Posts

Showing posts from January, 2021

Binary Search Tree - Iterative inorder tree walk

Image
Today, I’ll walk you through an iterative algorithm for inorder tree walk over a Binary search tree. First, let me draw your attention to an exercise in the CLRS book [1]. Exercise 12.1-3 Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes that we can test two pointers for equality.) The one which uses a stack is relatively simple. Here’s how it looks. **Input:** $root$ node of the tree $T$   $INORDER-TREEWALK-ITERATIVE(root)$   $\phantom{{}++{}}$ Let $s$ be an empty stack   $\phantom{{}++{}}$ TreeNode $\;\;current \gets root$   $\phantom{{}++{}}$  `while`$\;!s.isEmpty$ or $current \;\neq sentinel$   $\phantom{{}++{}}$  $\phantom{{}++{}}$ `if` $current \neq sentinel$   $\phantom{{}++{}}$  $\phantom{{}++{}}$ $\phantom{{}++{}}$  $s.push(current)$   $\phantom{{}++{}}$  $\phantom{{}++{}}$ $\phantom{{}++{}}$ $current \gets current.left$   $\p