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) ++ Let s be an empty stack ++ TreeNode current←root ++ `while`!s.isEmpty or current≠sentinel ++ ++ `if` current≠sentinel ++ ++ ++ s.push(current) ++ $\phantom{{}+...