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.

Trees 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
Pre order
Post Order

In order Traversal

Storing each element in an array while traversing

Level Order Traversal

// Iterative
while(!queue.isEmpty()){
    TreeNode temp = queue.poll();
    //Use the temp node

    if(temp.left != null)
      queue.add(temp.left);
    if(temp.right != null)
      queue.add(temp.right);
}

Height of a 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 Left Nodes

Number the nodes from top to bottom in Pro Order way.

Problem Statement

Remove leaf node

Count Empty Spots

Depth Sum

Complete to Level

Problem Statement

Top-Down Approach

Bottom-Up Approach

Isomorphic Trees

return (root1.val == root2.val) &&
        isIsomprphic(root1.left, root2.right) &&
        isIsomprphic(root1.right, root2.left)