Trees

1 minute read

//This if Condition ensures that the root is a branch (only one child)
if(root.left != null || root.right != null){
    if(root.data %2 == 0){
        count++;
    }
}

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.

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 (Lise BFS using a Queue)

In order Traversal in BST

Storing each element in an array while traversing

Level Order Traversal

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