Tree traversal

Depth first search:
  pre-order, implementation

1. Check if the current node is empty / null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function

preorder(node) if (node = null) return visit(node) preorder(node.left) preorder(node.right)

iterativePreorder(node) if (node = null) return s ← empty stack s.push(node) while (not s.isEmpty()) node ← s.pop() visit(node) //right child is pushed first so that left is processed first if (node.right ≠ null) s.push(node.right) if (node.left ≠ null) s.push(node.left)

  in-order, implementation

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

inorder(node) if (node = null) return inorder(node.left) visit(node) inorder(node.right)

iterativeInorder(node) s ← empty stack while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else node ← s.pop() visit(node) node ← node.right

  post-order, implementation

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

postorder(node) if (node = null) return postorder(node.left) postorder(node.right) visit(node)

iterativePostorder(node) s ← empty stack lastNodeVisited ← null while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else peekNode ← s.peek() // if right child exists and traversing node // from left child, then move right if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right) node ← peekNode.right else visit(peekNode) lastNodeVisited ← s.pop()

Breadth-first search:

  queue based:

levelorder(root)
  q ← empty queue
  q.enqueue(root)
  while (not q.isEmpty())
    node ← q.dequeue()
    visit(node)
    if (node.left ≠ null)
      q.enqueue(node.left)
    if (node.right ≠ null)
      q.enqueue(node.right)