In general, BST problems boil down to using the fact for a given node with value x, the value of the nodes on the left are ≤ x and the values of the nodes on the right are ≥ x.

• Traversal patterns:
  • inorder
  • postorder
  • preorder

Inorder traversal

Writing the recursive versions of the above traversal patterns are trivial. The most useful is inorder and its iterative implementation is preferred because recursion is easier and and each recursive call has to keep track of an at most $log(n)$ size stack.

One question that I was asked during an interview was to simply write a binary tree in order traversal without using recursion. Without looking below, really try to use come up with your own solution.

Once you have attempted it...

I have found this implementation to be the most clear and easy to work with:

def iterative_inorder(root: Node):
	cur = root
  stack = []
  ans = []
  while True:
      if cur:
          stack.append(cur)
          cur = cur.left
      else:
          if stack:
              next_smallest = stack.pop()
              ans.append(next_smallest.val)
              cur = next_smallest.right
          else:
              break
  return ans

With this Implementation, We can begin and answer LeetCode 94. Binary Tree Inorder Traversal.

Taking this a step further we can use these template and answer questions like LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List.

def treeToDoublyList(self, root: 'Node') -> 'Node':
        if root is None:
            return root
        head = tail = None
        
        cur = root
        stack = []
        while True:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                if stack:
                    small = stack.pop()
                    if head is None:
                        head = small
                        tail = small
                    else:
                        tail.right = small
                        small.left = tail
                        tail = small
                    cur = small.right
                else:
                    break
        head.left = tail
        tail.right = head
        return head