Construct Special Binary Tree from given Inorder traversal | GeeksforGeeks
Given Inorder Traversal of a Special Binary Tree in which key of every node is greater than keys in left and right children, construct the Binary Tree and return root.
Time Complexity: O(n^2)
1) Find index of the maximum element in array. The maximum element must be root of Binary Tree.
2) Create a new tree node ‘root’ with the data as the maximum value found in step 1.
3) Call buildTree for elements before the maximum element and make the built tree as left subtree of ‘root’.
5) Call buildTree for elements after the maximum element and make the built tree as right subtree of ‘root’.
6) return ‘root’.
Read full article from Construct Special Binary Tree from given Inorder traversal | GeeksforGeeks
Given Inorder Traversal of a Special Binary Tree in which key of every node is greater than keys in left and right children, construct the Binary Tree and return root.
Time Complexity: O(n^2)
1) Find index of the maximum element in array. The maximum element must be root of Binary Tree.
2) Create a new tree node ‘root’ with the data as the maximum value found in step 1.
3) Call buildTree for elements before the maximum element and make the built tree as left subtree of ‘root’.
5) Call buildTree for elements after the maximum element and make the built tree as right subtree of ‘root’.
6) return ‘root’.
struct node* buildTree (int inorder[], int start, int end){ if (start > end) return NULL; /* Find index of the maximum element from Binary Tree */ int i = max (inorder, start, end); /* Pick the maximum value and make it root */ struct node *root = newNode(inorder[i]); /* If this is the only element in inorder[start..end], then return it */ if (start == end) return root; /* Using index in Inorder traversal, construct left and right subtress */ root->left = buildTree (inorder, start, i-1); root->right = buildTree (inorder, i+1, end); return root;}