[LeetCode Solution 144] Binary Tree Preorder Traversal

[LeetCode 144]

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree,{1,#,2,3}

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

*****************************************************************************************************************

Solution:

[My Solution on LeetCode]

Approach #1 Recursive

Detail Explanation
The first method to solve this problem is using recursive.
This is the classical method and straightforward. we can define a helper function to implement recursion.
The java code is as follows:

Java

public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  helper(root, res);
  return res;
}

public void helper(TreeNode root, List<Integer> res) {
  if (root != null) {
    res.add(root.val);
    if (root.left != null) {
      helper(root.left, res);
    }
    if (root.right != null) {
      helper(root.right, res);
    }
  }
}

Complexity Analysis

Time complexity: \(O(n)\). The time complexity is \(O(n)\) because the recursive function is \(T(n) = 2*T(n/2)+1\).
Space complexity: The worst case is \(O(n)\), and the average case is \(O(log(n))\) where n is a number of nodes. A lot of people will have the question, why the worst case is \(O(n)\)?
it is because the space complexity is related to the height of the tree when the tree is balanced, the height is \(O(log(n))\), the worst case is \(O(n)\).

Approach #2 Iterating method using Stack

Detail Explanation
The strategy is very similar to the first method, the different is using a stack. For each node
if the node is not null, we add its value to the result, then if the node has the right child,
push the right in the stack and if the node has left a child, update node as its left child.
if the stack is not empty and the node is null, we update the node as stack.pop().

Here is an Example:

       1
     /   \
    2     3
   / \
  4   5
  
initial: res[]; curr = 1; stack[];
step1 : res[1]; curr = 2; stack[3];
step2 : res[1,2]; curr = 4; stack[3,5];
step3 : res[1,2,4]; curr = null; stack[3,5];
step4 : curr == null && stack is not empty -> curr = 5; stack[3];
step5 : res[1,2,4,5]; curr == null; stack[3];
step6 : curr == null && stack is not empty -> curr = 3; stack[];
step7 : res[1,2,4,5,3]; curr == null; stack is empty;
step8 : return [1,2,4,5,3]

Comment: the preorder traversal is root->root.left->root.right,
if the root.right is not null, we push it in the stack,
which make sure the order we process the right subtree,
this is the reason we use stack.

Java

class Solution {
 public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  TreeNode curr = root;
  while (curr != null) {
   res.add(curr.val);

   if (curr.right != null) {
    stack.push(curr.right);
   }
   curr = curr.left;
   if (curr == null && !stack.isEmpty()) {
    curr = stack.pop();
   }
  }
  return res;
 }
}

Complexity Analysis

Time complexity: \(O(n)\).
Space complexity: \(O(n)\).

Approach #3 Morris Traversal

Detail Explanation

This method we have to use a new data structure Threaded Binary Tree and the strategy is as follows:

Step1. Initialize current as root
Step2. While current is not NULL
 If current does not have left child
 a. Add current’s value
 b. Go to the right, i.e., current = current.right
Else
 a. add current's value.
 b. In current's left subtree, make current's right the right child of the rightmost node in left subtree.
 c. Go to this left child, i.e., current = current.left

For Example:
  curr->(1)
       /   \
      2     3
     / \   /
    4   5 6
res[];
First: 1 is the root, so initial 1 as current, 1 has left child which is 2, the current's left subtree is
        2
       / \
      4   5
so in this subtree, the rightmost node is 5, then make the current(1)'s right as the right child of 5. Set current = cuurent.left (current = 2).
The tree now looks like:
          1
         /
curr-> (2)
       / \
      4   5
           \
            3
            /
          6
res[1];
For current, 2, which has left child 4, so make the current's right as it's left subtree's right most node(4)'s right child
           1
          /
         2
        /
curr->(4)
        \
          5
           \
            3
            /
           6
res[1,2];
then add 4 because it has no left child, then add 5,3 one by one, for node 3 which has left child 6, do the same as above.
Finally, the inoder taversal is [1,2,4,5,3,6].

For more detail, please check

Threaded binary tree

Java

class Solution {
public List<Integer> preorderTraversal(TreeNode node) {
     List<Integer> list = new ArrayList();
     while(node != null) {
         if(node.left == null) {
             list.add(node.val);
             node = node.right;
         }
         else {
             TreeNode nextNode = node.left;

             TreeNode p = nextNode;
             while(p.right != null) p = p.right;

             list.add(node.val);
             p.right = node.right;
             node = nextNode;
         }
     }
     return list;
 }

}

Complexity Analysis

Time complexity: \(O(n)\).
Space complexity: \(O(n)\).

Prove

To prove that the time complexity is \(O(n)\), The biggest problem lies in finding the time complexity of finding the predecessor nodes of all the nodes in the binary tree. Intuitively, that complexity is \(O(nlogn)\), because to find the predecessor node for a single node related to the height of the tree.
But in fact, finding the predecessor nodes for all nodes only needs \(O(n)\) time. Because n nodes in a Binary-Tree have n-1 edges, the whole processing for each edges up to 2 times, one is to locate a node, and the other is to find the predecessor node. So the complexity is \(O(n)\).

The space complexity of Morris Traversal is \(O(1)\) because it just needs 2 "assisting" pointers. (TreeNode p and TreeNode nextNode) but we use \(O(n)\) list.

MY

Search This Blog