LeetCode - The Tree Part

The basic idea of tree related problems is to use recursion. If we can do it for left subtree and right subtree, we can do it for the whole tree.

The basic method to traversal the tree is BFS and DFS.

But if we need to know the node and the pre node in a BST at the same time. We can use Morris Inorder Traversal to get a O(1) SC.

The iteration version of preorder, inorder, postorder:

• preorder

void preorder(TreeNode root){
	if (root == null){
		return;
	}

	Stack<TreeNode> stack = new Stack<>();

	TreeNode node = root;

	while (!stack.isEmpty() || node != null){
		if (node != null){
			visit(node);
			stack.push(node);
			node = node.left;
		}
		else{
			node = stack.pop();
			node = node.right;
		}
	}
}

• inorder

void inorder(TreeNode root){
	if  (root == null){
		return;
	}

	TreeNode node = root;
	Stack<TreeNode> stack = new Stack<>();

	while (!stack.isEmpty() || node != null){
		if (node != null){
			stack.push(node);
			node = node.left;
		}
		else{
			node = stack.pop();
			visit(node);
			node = node.right;
		}
	}
}

• postorder

List<Integer> postorder(TreeNode root){
	LinkedList<Integer> res = new LinkedList<>();

	Stack<TreeNode> stack = new Stack<>();

	stack.push(root);
	while (!stack.isEmpty()){
		TreeNode node = stack.pop();

		res.addFirst(node.val);
		if (node.left != null){
			stack.push(node.left);
		}

		if (node.right != null){
			stack.push(node.right);
		}
	}

	return res;
}

DFS: we need an extra global pointer to save the previous one.

TreeNode pre = null;

void dfs(TreeNode node){
    if (node == null){
        return;
    }

    dfs(node.left);

    // traversal part
    
    // update pre
    pre = node;

    dfs(node.right);
}

BFS: don’t need global pointer.

Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode pred = null;

while (!stack.isEmpty() || root != null){
    while (root != null){
        stack.add(root);
        root = root.left;
    }

    root = stack.removeLast(); 


    // traversal part

    //update pred
    pred = root;

    root = root.right;
}

The TC of BFS and DFS are O(N), where N is the number of TreeNodes. And SC is O(H), where H is the height of the Tree.

And Morris Inorder Traversal can do the traversal with TC O(N) and SC O(1).

The idea of Morris algorithm is to set the temporary link between the node and its predecessor: predecessor.right = root. So one starts from the node, computes its predecessor and verifies if the link is present.

• There is no link? Set it and go to the left subtree.

• There is a link? Break it and go to the right subtree.

    void Morris(TreeNode root) 
	{ 
		TreeNode curr, prev; 

		if (root == null) 
			return; 

		curr = root; 
		while (curr != null) { 
			if (curr.left == null) { 
                // traversal part for the left node
				System.out.print(curr.data + " "); 
                
				curr = curr.right; 
			} 
			else { 
				/* Find the previous (prev) of curr */
				prev = curr.left; 
				while (prev.right != null && prev.right != curr) 
					prev = prev.right; 

				/* Make curr as right child of its prev */
				if (prev.right == null) { 
                    // traversal part for the right node
					prev.right = curr; 
					curr = curr.left; 
				} 

				/* fix the right child of prev*/
				else {
					prev.right = null; 

                    // traversal part for the root node
					System.out.print(curr.data + " "); 
					curr = curr.right; 
				} 

			} 

		}
	}