Binary Trees study guide

Prerequisites?that you should be familiar with before :?Recursion, stack, queue

A basic instinct for solving DFS based questions is to do a recursive call and for all BFS(level order traversal) is to make queue and iterate, but also think upon how to iterate in DFS(Hint think on stack) and recurse in BFS based.

First of all you should look at?traversal problems:

1. Inorder Traversal
2. Preorder Traversal
3. PostOrder Traversal
4. Level Order Traversal

A variation for LevelOrder can be:?ZigZag level order traversal?and?Binary Tree Level Order Traversal II

Solving these questions will help you get familiarized with basic btree dfs and bfs traversals.

Intuition for Level Order Traversal?iteratively using queue:

• Construct a queue of type: TreeNode?queue<TreeNode* > q, initially push the given root in it.
• Iterate through the queue until empty:
• Store the current size of queue?tempSize, this will be the size of the current level of the tree.
• Now we need to traverse this level so iterate for?tempSize>=0?:
• Pop the current element and apply the needed operation for the same and if left or right child exist then pass them to the queue.

Now, some basic Binary Tree problems that will help your thinking process:

1. Same Tree
2. Symmetric Tree
3. Maximum Depth of Binary Tree
4. Balanced Binary Tree
5. Minimum Depth of Binary Tree
6. Merge Two Binary Trees
7. Diameter of Binary Tree
8. Binary Tree Tilt
9. Invert Binary Tree

Binary Search Tree:?Use the property of BST judiciously (the left subtree will always contain nodes with value less than root's value and right subtree will contain nodes with value greater than root's value)

1. Search in a Binary Search Tree
2. Two Sum IV - Input is a BST
3. Minimum Absolute Difference in BST
4. Range Sum of BST
5. Delete Node in a BST
6. Trim a Binary Search Tree
7. Insert into a Binary Search Tree
8. Kth Smallest Element in a BST
9. All Elements in Two Binary Search Trees

Path problems:?You are given root, you have to perform operations on a path, (path is root to leaf). Think upon the type of traversal you will apply when going from root to leaf:

1. Binary Tree Paths
2. Path Sum
3. Path Sum II
4. Sum root to leaf numbers
5. Binary Tree Maximum Path Sum
6. *Path Sum III
7. *Pseudo-Palindromic Paths in a Binary Tree
8. *Last two problems here are utmost important

Next is, given a combination of preorder, postorder and inorder traversals, you need to?construct a binary tree/BST:

Hint: Observe in each traversal method, position of root and head of right and left subtrees

1. Construct Binary Tree from Preorder and Inorder Traversal
2. Construct Binary Tree from Inorder and Postorder Traversal
3. Construct Binary Tree from Preorder and Postorder Traversal
4. Convert Sorted Array to Binary Search Tree
5. Construct Binary Search Tree from Preorder Traversal

View problems:?Try thinking for left, bottom and top too!

Binary Tree Right Side View

Lowest Common Ancestor problems:?You are given two nodes and you have to return their ancestor at as least depth possible, these are problems are a must todo:

1. Lowest Common Ancestor of a Binary Tree
2. Lowest Common Ancestor of a Binary Search Tree
3. Lowest Common Ancestor of Deepest Leaves

Validate trees:

1. Validate Binary Tree Nodes
2. Validate Binary Search Tree

Some?miscellaneous?problems that you should definitely look through:

1. Flatten Binary Tree to Linked List
2. Count Complete Tree Nodes
3. Maximum Width of Binary Tree
4. Check Completeness of a Binary Tree
5. Cousins in Binary Tree
6. Maximum Difference Between Node and Ancestor
7. Number of Good Leaf Nodes Pairs
8. Smallest Subtree with all the Deepest Nodes
9. All Nodes Distance K in Binary Tree
10. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
11. Vertical Order Traversal of a Binary Tree

I will be updating this list on finding more important questions or any pattern that I find.

#binaryTree #binarytreeguide #leetcode #datastructure #placementpreparation #codingisfun #binarysearchtree