Binary Tree Question Summary

Traverse of the binary tree

In general, there are fours ways to traverse a tree, they are pre-order, in-order, post-order, and level-order. For the first three ways, we can do it clearly by using recursive as below.

void traverseTree(TreeNode* root) {
	// base case of recursive
	cout << root->value;      /*❶*/
	traverseTree(root->left);
	cout << root->value;      /*❷*/
	traverseTree(root->right);
	cout << root->value;      /*❸*/
}

❶ visit root value here is pre-order
❷ visit root value here is in-order
❸ visit root value here is post-order
So for a tree as below, we can have three traverse result:

pre-order: [5, 4, 2, 0, 1, 6, 3]
in-order: [2, 0, 4, 1, 5, 6, 3]
post-order: [0, 2, 1, 4, 3, 6, 5]
And level order traverse is simple: [5, 4, 6, 2, 1, 3, 0]

Categories of binary tree question

• General binary tree/binary search tree recursive question. Almost 99% of the binary tree question can be solved in recursive way. And there are three kind of question in general.
  • pass the result value from top down to bottom.
    Eg. Check valid BST( leetcode 98)
  • pass the result value from bottom to top.
    Eg. Get Height of the tree. Check tree is balanced (leetcode 110). Check tree is symmetric (leetcode 101). Assign the value of each node to be the total number of nodes that belong to its left substree.
  • Pass the help value from bottom to top, and meanwhile update the result according to the help value. Most hard problem can be done by this approach. and there are many questions in leetcode you can practice.
• Rebuild tree
  Use two kinds of traverse result to rebuild the tree.
• Serialize the tree structure.
• Binary search tree
  To use BST properties to solve the problem.
• Level order traverse question

Key points

1. Have to decide which kind of traverse we gonna use. Eg. if it is BST and we want to leverage the ordered property of the BST. In-order traverse is nice to use. if we want the value from left subtree and right subtree, post order is good to use.
2. Decide what operations we need to do for current node. Eg. What values we need to return? how we update the result value? What relationship among root and its left subtree, right subtree.

Question List

We are keep tracking the binary search tree question, I will try to categorize each question. Another thing good to mention is many question can be solve in different way, but they all fits in categories we talked above.