Question

*** using java application

Q1. BST: 1. Write a method that takes an array A, as parameter (A contains the elements of a BST traversed in preorder) and returns the corresponding BST 2. Write a method to list the nodes on the path from the root to a given node in the BST. 3. Write a recursive method to check if two BSTs are same. 4. Write a non-recursive method to check if two BSTs are same 5. Write a method to count the number of nodes in BST with a single child. 6. Write the main program to test your methods.

Answer 1

Following are the things we need to keep into consideration.

1. For the first function, we need to use the preorder array given and use it to form the tree.
2. We need to find the value which will be passed to the function and find the value based on the property of BST and then print all the nodes in the path.
3. Recursive method to check if both the tree are the same or not, check for each node and then recursively call for left and right.
4. Same non-recursive function in using the stack.
5. Next function is to count the nodes with just one child.
   1. if there are two nodes then call the function for the left and right child.
   2. if have one child then add 1 to return as well call for the child which is present.
   3. If no child then returns 0.

Following is the code for the same in JAVA>

// Java program to construct BST from given preorder traversal

import java.util.*;

// A binary tree node
class Node {

   int data;
   Node left, right;

   Node(int d) {
       data = d;
       left = right = null;
   }
}

class BinaryTree {

   // The main function that constructs BST from array[]
   Node constructTree(int array[], int size) {

       Node root = new Node(array[0]);

       Stack<Node> s = new Stack<Node>();

       // Push root
       s.push(root);

       // Iterate through rest preorder array
       for (int i = 1; i < size; ++i) {
           Node temp = null;
           while (!s.isEmpty() && array[i] > s.peek().data) {
               temp = s.pop();
           }
           if (temp != null) {
               temp.right = new Node(array[i]);
               s.push(temp.right);
           }
           else {
               temp = s.peek();
               temp.left = new Node(array[i]);
               s.push(temp.left);
           }
       }

       return root;
   }

   // A utility function to print inorder traversal of a Binary Tree
   void printInorder(Node node) {
       if (node == null) {
           return;
       }
       printInorder(node.left);
       System.out.print(node.data + " ");
       printInorder(node.right);
   }
   // function for printing the nodes which are coming in the path of data
   void printNodesInPath(Node node, int data) {
       if(node == null) {
           return;
       }
       if(node.data == data) {
           return;
       }
       System.out.print(node.data+" ");
       if(node.data < data) {
           printNodesInPath(node.right, data);
       }else {
           printNodesInPath(node.left, data);
       }
   }
   // this is the function for checking if both the trees
   // passed are same or not using a recursive function
   boolean checkRecIfSame(Node node1, Node node2) {
       if(node1==null && node2==null) {
           return true;
       }else if(node1 == null || node2 ==null) {
           return false;
       }
       if(node1.data != node2.data) {
           return false;
       }else {
           return checkRecIfSame(node1.left, node2.left) && checkRecIfSame(node1.right, node2.right);
       }
   }
   // This is same as the above function,
   // but a non-recursive funciton using the stack
   boolean checkNonRecIfSame(Node node1, Node node2) {
       Stack<Node> s1 = new Stack<Node>(), s2 = new Stack<Node>();
       if(node1 == null && node2 == null) {
           return true;
       }
       if(node1 == null || node2 == null) {
           return false;
       }
       s1.push(node1);s2.push(node2);
       while(!s1.isEmpty() && !s2.isEmpty()) {
           Node n1 = s1.pop(), n2 = s2.pop();
           if(n1.data != n2.data) {
               return false;
           }
           if(n1.left != null) {
               s1.push(n1.left);
           }
           if(n1.right != null) {
               s1.push(n1.right);
           }
           if(n2.left != null) {
               s2.push(n2.left);
           }
           if(n2.right != null) {
               s2.push(n2.right);
           }
       }
       if(s1.isEmpty() && s2.isEmpty()) {
           return true;
       }else {
           return false;
       }
      
   }
   // here in this function to count the number of nodes
   // with one child
   int countNodesWithSingleChild(Node node) {
       if(node == null) {
           return 0;
       }else if(node.left != null && node.right != null) {
           return countNodesWithSingleChild(node.left) + countNodesWithSingleChild(node.right);
       }
       else if(node.left == null && node.right == null) {
           return 0;
       }else if(node.right == null) {
           return 1+countNodesWithSingleChild(node.left);
       }else {

           return 1+countNodesWithSingleChild(node.right);
       }
   }
   // Driver program to test above functions
   public static void main(String[] args) {
       BinaryTree tree1 = new BinaryTree();
       int array1[] = new int[]{310, 35, 31, 37, 340, 350};
       int size = array1.length;
       Node root1 = tree1.constructTree(array1, size);
       System.out.print("Inorder traversal of the constructed tree is ");
       tree1.printInorder(root1);
       System.out.println();
       BinaryTree tree2 = new BinaryTree();
       int array2[] = new int[]{310, 35, 31, 37, 340, 350};
       int size2 = array1.length;
       Node root2 = tree1.constructTree(array2, size2);
       System.out.print("Inorder traversal of the constructed tree is ");
       tree1.printInorder(root2);
       System.out.println();
       System.out.print("Nodes In the path are: ");
       tree1.printNodesInPath(root1, 350);
      
       System.out.println("Checking if both trees are same with recursive function: " + tree1.checkRecIfSame(root1, root2));;
       System.out.println("Checking if both trees are same with recursive function: " + tree1.checkNonRecIfSame(root1, root2));
       System.out.println("Counting the number of nodes with one child: " + tree1.countNodesWithSingleChild(root1));
   }
}

terminated> Binary TreeJava Application] C:Program Files Java jre1.8.0 171\bin javaw.exe (May 5, 2019, 12:43.19 AM) Inorder traversal of the constructed tree is 31 35 37 310 340 350 Inorder traversal of the constructed tree is 31 35 37 310 340 350 Nodes In the path are: 310 340 Checking if both trees are same with recursive function: true Checking if both trees are same with recursive function: true Counting the number of nodes with one child:1

Thanks