Binary Trees (DFS & BFS)

3 minute read

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:
    1. every element of R’s left subtree contains data “less than” R’s data,
    2. every element of R’s right subtree contains data “greater than” R’s,
    3. 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

  • 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. ```java 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](https://www.codestepbystep.com/r/problem/view/java/collectionimpl/binarytrees/height)
<script src="https://gist.github.com/nitinkc/5837831baee94bd7a6bbe0b58f050197.js"> </script>

### Remove leaf node
<script src="https://gist.github.com/nitinkc/cb357a5e77be6236be35afef0c398953.js"> </script>

### Find Level of a Given Node in a Binary Tree
<script src="https://gist.github.com/nitinkc/00c46d469167c099679682c41e6b24e8.js"> </script>

### Print nodes at a level
Given a Tree and the depth/level, print all the nodes from left to right.
<script src="https://gist.github.com/nitinkc/f34b9a1134477b0f1cbc22e777fab7e2.js"> </script>

### Print Leaves Nodes from Right to Left
<script src="https://gist.github.com/nitinkc/5934eb3d94794c23106f38e17aaa61f1.js"> </script>

### [Count all Leaf Nodes](https://www.codestepbystep.com/r/problem/view/java/collectionimpl/binarytrees/countLeaves)
<script src="https://gist.github.com/nitinkc/e180867eb09c229d72ef3df06333401e.js"> </script>

### [Count Left Nodes](https://www.codestepbystep.com/r/problem/view/java/collectionimpl/binarytrees/countLeftNodes)
<script src="https://gist.github.com/nitinkc/8ac5f8599a620d6e860228c15798f023.js"> </script>

### [Number the nodes in Pre Order way](https://www.codestepbystep.com/r/problem/view/java/collectionimpl/binarytrees/numberNodes)
<script src="https://gist.github.com/nitinkc/87f93c0ac63b4b5e8eaa51d9166b6585.js"> </script>

### Count Empty Spots
<script src="https://gist.github.com/nitinkc/619d22e2ae458a3f174b0297019e6fd5.js"> </script>

### Depth Sum
- For Iterative, BFS approach, the size of the queue has all elements at the same level
  ```java
  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 ```java //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) ```

You may also enjoy