fork download
copy 
  1. // Java program to construct BST from given preorder traversal
  2.  
  3. // A binary tree node
  4. class Node {
  5.  
  6.     int data;
  7.     Node left, right;
  8.  
  9.     Node(int d) {
  10.         data = d;
  11.         left = right = null;
  12.     }
  13. }
  14.  
  15. class Index {
  16.  
  17.     int index = 0;
  18. }
  19.  
  20. class BinaryTree {
  21.  
  22.     Index index = new Index();
  23.  
  24.     // A recursive function to construct Full from pre[]. preIndex is used
  25.     // to keep track of index in pre[].
  26.     Node constructTreeUtil(int pre[], Index preIndex,
  27.             int low, int high, int size) {
  28.  
  29.         // Base case
  30.         if (preIndex.index >= size || low > high) {
  31.             return null;
  32.         }
  33.  
  34.         // The first node in preorder traversal is root. So take the node at
  35.         // preIndex from pre[] and make it root, and increment preIndex
  36.         Node root = new Node(pre[preIndex.index]);
  37.         preIndex.index = preIndex.index + 1;
  38.  
  39.         // If the current subarry has only one element, no need to recur
  40.         if (low == high) {
  41.             return root;
  42.         }
  43.  
  44.         // Search for the first element greater than root
  45.         int i;
  46.         for (i = low; i <= high; ++i) {
  47.             if (pre[i] > root.data) {
  48.                 break;
  49.             }
  50.         }
  51.  
  52.         // Use the index of element found in preorder to divide preorder array in
  53.         // two parts. Left subtree and right subtree
  54.         root.left = constructTreeUtil(pre, preIndex, preIndex.index, i - 1, size);
  55.         root.right = constructTreeUtil(pre, preIndex, i, high, size);
  56.  
  57.         return root;
  58.     }
  59.  
  60.     // The main function to construct BST from given preorder traversal.
  61.     // This function mainly uses constructTreeUtil()
  62.     Node constructTree(int pre[], int size) {
  63.         return constructTreeUtil(pre, index, 0, size - 1, size);
  64.     }
  65.  
  66.     // A utility function to print inorder traversal of a Binary Tree
  67.     void printInorder(Node node) {
  68.         if (node == null) {
  69.             return;
  70.         }
  71.         printInorder(node.left);
  72.         System.out.print(node.data + " ");
  73.         printInorder(node.right);
  74.     }
  75.  
  76.     // Driver program to test above functions
  77.     public static void main(String[] args) {
  78.         BinaryTree tree = new BinaryTree();
  79.         int pre[] = new int[]{10, 5, 1, 7, 40, 50};
  80.         int size = pre.length;
  81.         Node root = tree.constructTree(pre, size);
  82.         System.out.println("Inorder traversal of the constructed tree is ");
  83.         tree.printInorder(root);
  84.     }
  85. }
Success #stdin #stdout 0.1s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder traversal of the constructed tree is 
1 5 7 10 40 50
https://ideone.com/ULdhUV
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!