Binary Trees

2 minute read

Summary

ensures that the root is a branch (only one child)

if(root.left != null || root.right != null){
  if(root.data %2 == 0){
      count++;
  }
}

For BFS (level order traversal), a Queue is used as intermediate data structure.

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);//Begin with root
while(!queue.isEmpty()){
temp = queue.poll();//Take the top of queue
.....
if(temp.left != null)//Add the LEFT first to the queue, so that it is processed before the right child
  queue.add(temp.left);
if(temp.right != null)
  queue.add(temp.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

Binary Search

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)
    binarySearchRecursive(arr, mid + 1, end, value);
else if  (arr[mid] > value)
    binarySearchRecursive(arr, 0, mid - 1, value);   
else
    return mid;           

Good Problems

Height of a Tree

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 from top to bottom in Pre Order way.

Problem Statement

Remove leaf node

Count Empty Spots

Depth Sum

Iterative

If you calculate the size of the queue, the current size 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