Question: 3. Binary search trees (a) Given a binary tree, give efficient algorithms to determine (i) the to……

(a) (i) Ans:- The idea is to use level-order traversal to solve this problem efficiently.

1) Create an empty Queue Node and push root node to Queue.
2) Do following while nodeQeue is not empty.
   a) Pop an item from Queue and process it.
      a.1) If it is full node then increment count++.
   b) Push left child of popped item to Queue, if available.
   c) Push right child of popped item to Queue, if available.

Implementation in Java:

// Java program to count

// full nodes in a Binary Tree

// using Iterative approach

import java.util.Queue;

import java.util.LinkedList;

 

// Class to represent Tree node

class Node

{

int data;

Node left, right;

 

public Node(int item)

{

data = item;

left = null;

right = null;

}

}

 

// Class to count full nodes of Tree

class BinaryTree

{

 

Node root;

 

/* Function to get the count of full Nodes in

a binary tree*/

int getfullCount()

{

// If tree is empty

if (root==null)

return 0;

 

// Initialize empty queue.

Queue<Node> queue = new LinkedList<Node>();

// Do level order traversal starting from root

queue.add(root);

 

int count=0; // Initialize count of full nodes

while (!queue.isEmpty())

{

 

Node temp = queue.poll();

if (temp.left!=null && temp.right!=null)

count++;

 

// Enqueue left child

if (temp.left != null)

{

queue.add(temp.left);

}

 

// Enqueue right child

if (temp.right != null)

{

queue.add(temp.right);

}

}

return count;

}

 

public static void main(String args[])

{

BinaryTree tree_level = new BinaryTree();

tree_level.root = new Node(2);

tree_level.root.left = new Node(7);

tree_level.root.right = new Node(5);

tree_level.root.left.right = new Node(6);

tree_level.root.left.right.left = new Node(1);

tree_level.root.left.right.right = new Node(11);

tree_level.root.right.right = new Node(9);

tree_level.root.right.right.left = new Node(4);

 

System.out.println(tree_level.getfullCount());

 

}

}

Time Complexity: O(n)

Auxiliary Space: O(n) where n is number of nodes in given binary tree

 

(a) (ii) Ans:-  Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1.

Algorithm :

  

maxDepth()
1. If tree is empty then return 0
2. Else
     (a) Get the max depth of left subtree recursively  i.e., 
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e., 
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right 
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,  
                             max depth of right subtree) 
                             + 1
     (d) Return max_depth

Time Complexity: O(n)

See the below diagram for more clarity about the execution of the recursive function maxDepth() for above example tree.

maxDepth('1') = max(maxDepth('2'), maxDepth('3')) + 1
                               = 2 + 1
                                  /    
                                /         
                              /             
                            /                 
                          /                     
               maxDepth('2') = 1                maxDepth('3') = 1
= max(maxDepth('4'), maxDepth('5')) + 1
= 1 + 1   = 2         
                   /    
                 /        
               /            
             /                
           /                    
 maxDepth('4') = 1     maxDepth('5') = 1

Implementation in Java:

// Java program to find height of tree

 

// A binary tree node

class Node

{

int data;

Node left, right;

 

Node(int item)

{

data = item;

left = right = null;

}

}

 

class BinaryTree

{

Node root;

 

/* Compute the “maxDepth” of a tree — the number of

nodes along the longest path from the root node

down to the farthest leaf node.*/

int maxDepth(Node node)

{

if (node == null)

return 0;

else

{

/* compute the depth of each subtree */

int lDepth = maxDepth(node.left);

int rDepth = maxDepth(node.right);

 

/* use the larger one */

if (lDepth > rDepth)

return (lDepth + 1);

else

return (rDepth + 1);

}

}

 

/* Driver program to test above functions */

public static void main(String[] args)

{

BinaryTree tree = new BinaryTree();

 

tree.root = new Node(1);

tree.root.left = new Node(2);

tree.root.right = new Node(3);

tree.root.left.left = new Node(4);

tree.root.left.right = new Node(5);

 

System.out.println(“Height of tree is : ” +

tree.maxDepth(tree.root));

}

}

Analyze:-   

The height of the binary tree is the longest path from root node to any leaf node in the tree. For example, the height of binary tree is 2 as longest path from root node to node 2 is 2. Also, the height of binary tree is 4.

Binary Tree –
In a binary tree, a node can have maximum two children.

Calculating minimum and maximum height from number of nodes –
If there are n nodes in binary tree, maximum height of the binary tree is n-1 and minimum height isfloor(log2n).

For example, left skewed binary tree with 5 nodes has height 5-1 = 4 and binary tree with 5 nodes has height floor(log25) = 2.

Calculating minimum and maximum number of nodes from height –
If binary tree has height h, minimum number of nodes is n+1 (in case of left skewed and right skewed binary tree).

Binary Search Tree –
In a binary search tree, left child of a node has value less than the parent and right child has value greater than parent.

Calculating minimum and maximum height from the number of nodes –
If there are n nodes in a binary search tree, maximum height of the binary search tree is n-1 and minimum height is floor(log2n).