Binary Search Tree - Iterative inorder tree walk
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