Preorder traversal on binary tree

2018-04-19

Content:

1. Problem statement

Given a binary tree, print its node values in preorder traversal.

Figure 1. Preorder of this binary tree is 2 7 2 6 5 11 5 9 4
(Source: Wikipedia - Binary tree)

2. Solution

Preorder traversal means we visit the tree in root, left, right order: the root node is visited first (thus the word pre), then its left and right child.

3. Implementation

3.1. Recursion

1
2
3
4
5
6
7

void preorder(TreeNode* root) {
  if (root == NULL) return;

  print("%d ", root->val);
  preorder(root->left);
  preorder(root->right);
}

Let’s call N is the number of nodes, H is the height of the tree.

  • Time complexity: $ O(N)$ since each node is visited exactly once.
  • Space complexity: $ O(H)$, the call stack can reach H in depth and each recursive call needs $ O(1)$ to store its parameters.

3.2. Iteration

Using stack:

1
2
3
4
5
6
7
8
9
10
11

void preorder(TreeNode* root) {
  stack<TreeNode*> stack({root});
  while(!stack.empty()) {
    TreeNode* node = stack.top();
    stack.pop();
    if (node == NULL) continue;
    print("%d ", node->val);  // visit node
    stack.push(node->right);  // push right first..
    stack.push(node->left);   // ..then push left, so that left is visited before right
  }
}
  • Time complexity: $ O(N)$ since each node is visited exactly once.
  • Space complexity: Space complexity is the maximum size of stack.
    • If the binary tree is skewed, space complexity will be $ O(1)$.
    • Now imagine a binary tree is composed of complete left-skewed sub trees: for example the complete left-skewed sub trees (i.e. a path from root to leaf node by constantly turning left) of the binary tree in Figure 1 are 2 7 2, 6 5, 11, 5, 9 4. We can present any path from the root to some node as the form (not neccesarily complete) left-skewed sub tree, turn right, left-skewed sub tree, turn right..: for example the path from root 2 to leaf node 5 can be represented as 2 7 turn right 6 5. Notice that on a path from root to some node, the stack will store the right child of nodes on the left-skewed trees (except for nodes where we turn right. In the worst case: this path will be a complete left-skewed sub stree, each node on this sub tree has a right child and the length of this sub tree is H, the space complexity is now $ O(H)$.
    • Conclusion: $ O(1)$ if the binary tree is skewed, $ O(H)$ in average and worst case.

4. Properties

  • Two binary trees have the same structure if and only if they have the same preorder traversal.

5. Practice