Binary Trees (DFS & BFS)
Summary
ensures that the root is a branch (has atleast one child)
if(root.left != null || root.right != null){//Condition for non leaf node
count++;//Counting non leaf nodes
}
- Whenever a path from root to leaf is required, DFS is the way to go.
- For BFS of a Tree, a Queue is used as intermediate data structure.
- regular (without level order) O(n), where n is the number of nodes in the tree. Each node is visited once.
Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ TreeNode temp = q.poll(); if(temp.left == null && temp.right == null) count++;//Counting number of leaf nodes if(temp.left != null) q.add(temp.left); if(temp.right != null) q.add(temp.right); } - when calculation to be done at the same level (Level Order, additional for loop)
- O(n), where n is the number of nodes. Each node is still visited exactly once; the extra for loop just processes all nodes at the current level before moving to the next.
Queue<TreeNode> queue = new LinkedList<>(); queue.add(root);//Begin with root while(!queue.isEmpty()){ int size = queue.size();// number of nodes at current level for(int i = 0; i < size; i++){ // Only when all calculation is to be done in the same level. TreeNode current = queue.poll(); if(current.left != null) queue.add(current.left); //For BFS, first left, then right if(current.right != null) queue.add(current.right); } .... }
Tree Traversal
Three types of Depth First Search (DFS) Traversal.
- For Iterative traversal, a Stack is used as intermediate data structure.
-
With Recursive Approach, recursion stack takes care
- InOrder (L,Root,R)
inOrder(root.left, list); list.add(root.data); inOrder(root.right,list); - Pre order (Root,L,R)
list.add(root.data); preOrder(root.left, list); preOrder(root.right,list); - Post Order (L,R,Root)
inOrder(root.left, list); inOrder(root.right,list); list.add(root.data); - Level Order Traversal (Like BFS using a Queue - Iterative)
Binary Search Tree
“BST”: a binary tree that is either:
- empty (null), or
- a root node R such that:
- every element of R’s left subtree contains data “less than” R’s data,
- every element of R’s right subtree contains data “greater than” R’s,
- R’s left and right subtrees are also binary search trees.
BSTs store their elements in sorted order, which is helpful for searching/sorting tasks. Storing each element in an array while traversing
Binary Search
-
int mid = (start + end) / 2;works for most cases, but it can cause integer overflow if start and end are large. -
int mid = start + (end - start) / 2;avoids overflow by calculating the midpoint without directly adding start and end together.
int binarySearchRecursive(int[] arr, int start, int end, int value)
/* Base Case when start > end */
if (start > end)
return -1;// value not found. Index = -1
int mid = (start + end) / 2;
if (arr[mid] < value)
return binarySearchRecursive(arr, mid + 1, end, value);
else if (arr[mid] > value)
return binarySearchRecursive(arr, 0, mid - 1, value);
else
return mid;
Good Problems
Height of a Tree
Remove leaf node
Find Level of a Given Node in a Binary Tree
Print nodes at a level
Given a Tree and the depth/level, print all the nodes from left to right.
Print Leaves Nodes from Right to Left
Count all Leaf Nodes
Count Left Nodes
Number the nodes in Pre Order way
Count Empty Spots
Depth Sum
- For Iterative, BFS approach, the size of the queue has all elements at the same level
int nodesAtLevel = q.size(); for(int i = 0; i < nodesAtLevel; i++){ //Do something with the nodes at the same level }
Complete to Level
-
Top-Down Approach
- keeps current depth and stops at n; creates missing children before recursing.
-
Bottom-Up Approach
- Bottom-up (remaining-level style): decrements level until it reaches 1; creates missing nodes along the way.
Isomorphic Trees
- notice the AND and then OR conditon in the first 2 if conditions
//base case,
if(root1 == null && root2 == null) return true;
//Cases like [1,null,2]
if(root1 == null || root2 == null) return false;
if(p.val != q.val) return false;
if(root1.val == root2.val) return true;
return isIsomprphic(root1.left, root2.right) &&
isIsomprphic(root1.right, root2.left)