Check if given inorder and preorder traversals are valid for any Binary Tree without building the tree
cGiven two arrays pre[] and in[] representing the preorder and inorder traversal of the binary tree, the task is to check if the given traversals are valid for any binary tree or not without building the tree. If it is possible, then print Yes. Otherwise, print No.
Examples:
Input: pre[] = {1, 2, 4, 5, 7, 3, 6, 8}, in[] = {4, 2, 5, 7, 1, 6, 8, 3}
Output: Yes
Explanation:
Both traversals are valid for the following binary tree:
1
/ \
2 3
/ \ /
4 5 6
\ \
7 8Input: pre[] = {1, 2, 69, 5, 7, 3, 6, 8}, in[] = {4, 2, 5, 7, 1, 6, 8, 3}
Output: No
Approach: The idea is to use similar technique to build the binary tree from inorder and preorder traversals, except that not to build the tree, rather to check if the current inorder traversal of that tree(subtree) and the current preorder Index is valid or not in each recursive call or not.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // C++ program to check if given inorder // and preorder traversals of size N are // valid for a binary tree or not bool checkInorderPreorderUtil( int inStart, int inEnd, int & preIndex, int preorder[], unordered_map< int , int >& inorderIndexMap) { if (inStart > inEnd) return true ; // Build the current Node int rootData = preorder[preIndex]; preIndex++; // If the element at current Index // is not present in the inorder // then tree can't be built if (inorderIndexMap.find(rootData) == inorderIndexMap.end()) return false ; int inorderIndex = inorderIndexMap[rootData]; // If the inorderIndex does not fall // within the range of the inorder // traversal of the current tree // then return false if (!(inStart <= inorderIndex && inorderIndex <= inEnd)) return false ; int leftInorderStart = inStart; int leftInorderEnd = inorderIndex - 1; int rightInorderStart = inorderIndex + 1; int rightInorderEnd = inEnd; // Check if the left subtree can be // built from the inorder traversal // of the left subtree and preorder if (!checkInorderPreorderUtil( leftInorderStart, leftInorderEnd, preIndex, preorder, inorderIndexMap)) return false ; // Check if the left subtree can be // built from the inorder traversal // of the left subtree and preorder else return checkInorderPreorderUtil( rightInorderStart, rightInorderEnd, preIndex, preorder, inorderIndexMap); } // Function to check for the validation of // inorder and preorder string checkInorderPreorder( int pre[], int in[], int n) { unordered_map< int , int > inorderIndexMap; for ( int i = 0; i < n; i++) inorderIndexMap[in[i]] = i; int preIndex = 0; if (checkInorderPreorderUtil( 0, n - 1, preIndex, pre, inorderIndexMap)) { return "Yes" ; } else { return "No" ; } } // Driver Code int main() { int pre[] = { 1, 2, 4, 5, 7, 3, 6, 8 }; int in[] = { 4, 2, 5, 7, 1, 6, 8, 3 }; int N = sizeof (pre) / sizeof (pre[0]); cout << checkInorderPreorder(pre, in, N); return 0; } |
Java
// Java program to check if given inorder // and preorder traversals of size N are // valid for a binary tree or not import java.util.*; class GFG { static int preIndex; static HashMap<Integer,Integer> inorderIndexMap = new HashMap<Integer,Integer>(); static boolean checkInorderPreorderUtil( int inStart, int inEnd, int preorder[]) { if (inStart > inEnd) return true ; // Build the current Node int rootData = preorder[preIndex]; preIndex++; // If the element at current Index // is not present in the inorder // then tree can't be built if (!inorderIndexMap.containsKey(rootData)) return false ; int inorderIndex = inorderIndexMap.get(rootData); // If the inorderIndex does not fall // within the range of the inorder // traversal of the current tree // then return false if (!(inStart <= inorderIndex && inorderIndex <= inEnd)) return false ; int leftInorderStart = inStart; int leftInorderEnd = inorderIndex - 1 ; int rightInorderStart = inorderIndex + 1 ; int rightInorderEnd = inEnd; // Check if the left subtree can be // built from the inorder traversal // of the left subtree and preorder if (!checkInorderPreorderUtil( leftInorderStart, leftInorderEnd,preorder)) return false ; // Check if the left subtree can be // built from the inorder traversal // of the left subtree and preorder else return checkInorderPreorderUtil( rightInorderStart, rightInorderEnd, preorder); } // Function to check for the validation of // inorder and preorder static String checkInorderPreorder( int pre[], int in[], int n) { //HashMap<Integer,Integer> inorderIndexMap = new HashMap<Integer,Integer>(); for ( int i = 0 ; i < n; i++) inorderIndexMap.put(in[i], i); preIndex = 0 ; if (checkInorderPreorderUtil( 0 , n - 1 , pre)) { return "Yes" ; } else { return "No" ; } } // Driver Code public static void main(String[] args) { int pre[] = { 1 , 2 , 4 , 5 , 7 , 3 , 6 , 8 }; int in[] = { 4 , 2 , 5 , 7 , 1 , 6 , 8 , 3 }; int N = pre.length; System.out.print(checkInorderPreorder(pre, in, N)); } } // This code is contributed by shikhasingrajput |
Python3
# Python program to check if given inorder # and preorder traversals of size N are # valid for a binary tree or not def checkInorderPreorderUtil(inStart, inEnd, preIndex, preorder, inorderIndexMap): if (inStart > inEnd): return True # Build the current Node rootData = preorder[preIndex] preIndex + = 1 # If the element at current Index # is not present in the inorder # then tree can't be built if (rootData in inorderIndexMap): return False inorderIndex = inorderIndexMap[rootData] # If the inorderIndex does not fall # within the range of the inorder # traversal of the current tree # then return false if ((inStart < = inorderIndex and inorderIndex < = inEnd) = = False ): return False leftInorderStart = inStart leftInorderEnd = inorderIndex - 1 rightInorderStart = inorderIndex + 1 rightInorderEnd = inEnd # Check if the left subtree can be # built from the inorder traversal # of the left subtree and preorder if (checkInorderPreorderUtil(leftInorderStart,leftInorderEnd,preIndex,preorder,inorderIndexMap) = = False ): return False # Check if the left subtree can be # built from the inorder traversal # of the left subtree and preorder else : return checkInorderPreorderUtil(rightInorderStart, rightInorderEnd,preIndex, preorder, inorderIndexMap) # Function to check for the validation of # inorder and preorder def checkInorderPreorder(pre, inv,n): inorderIndexMap = {} for i in range (n): inorderIndexMap[inv[i]] = i preIndex = 0 if (checkInorderPreorderUtil( 0 , n - 1 , preIndex,pre, inorderIndexMap)): return "No" else : return "Yes" # Driver Code if __name__ = = '__main__' : pre = [ 1 , 2 , 4 , 5 , 7 , 3 , 6 , 8 ] inv = [ 4 , 2 , 5 , 7 , 1 , 6 , 8 , 3 ] N = len (pre) print (checkInorderPreorder(pre, inv, N)) # This code is contributed by ipg2016107. |
C#
// C# program to check if given inorder // and preorder traversals of size N are // valid for a binary tree or not using System; using System.Collections.Generic; public class GFG { static int preIndex; static Dictionary< int , int > inorderIndexMap = new Dictionary< int , int >(); static bool checkInorderPreorderUtil( int inStart, int inEnd, int []preorder) { if (inStart > inEnd) return true ; // Build the current Node int rootData = preorder[preIndex]; preIndex++; // If the element at current Index // is not present in the inorder // then tree can't be built if (!inorderIndexMap.ContainsKey(rootData)) return false ; int inorderIndex = inorderIndexMap[rootData]; // If the inorderIndex does not fall // within the range of the inorder // traversal of the current tree // then return false if (!(inStart <= inorderIndex && inorderIndex <= inEnd)) return false ; int leftInorderStart = inStart; int leftInorderEnd = inorderIndex - 1; int rightInorderStart = inorderIndex + 1; int rightInorderEnd = inEnd; // Check if the left subtree can be // built from the inorder traversal // of the left subtree and preorder if (!checkInorderPreorderUtil( leftInorderStart, leftInorderEnd,preorder)) return false ; // Check if the left subtree can be // built from the inorder traversal // of the left subtree and preorder else return checkInorderPreorderUtil( rightInorderStart, rightInorderEnd, preorder); } // Function to check for the validation of // inorder and preorder static String checkInorderPreorder( int []pre, int []inn, int n) { // Dictionary<int,int> inorderIndexMap = new Dictionary<int,int>(); for ( int i = 0; i < n; i++) inorderIndexMap.Add(inn[i], i); preIndex = 0; if (checkInorderPreorderUtil( 0, n - 1, pre)) { return "Yes" ; } else { return "No" ; } } // Driver Code public static void Main(String[] args) { int []pre = { 1, 2, 4, 5, 7, 3, 6, 8 }; int []inn = { 4, 2, 5, 7, 1, 6, 8, 3 }; int N = pre.Length; Console.Write(checkInorderPreorder(pre, inn, N)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach let inorderIndexMap = new Map(); let preIndex; function checkInorderPreorderUtil( inStart, inEnd, preorder) { if (inStart > inEnd) return true ; // Build the current Node let rootData = preorder[preIndex]; preIndex++; // If the element at current Index // is not present in the inorder // then tree can't be built if (!inorderIndexMap.has(rootData)) return false ; let inorderIndex = inorderIndexMap.get(rootData); // If the inorderIndex does not fall // within the range of the inorder // traversal of the current tree // then return false if (!(inStart <= inorderIndex && inorderIndex <= inEnd)) return false ; let leftInorderStart = inStart; let leftInorderEnd = inorderIndex - 1; let rightInorderStart = inorderIndex + 1; let rightInorderEnd = inEnd; // Check if the left subtree can be // built from the inorder traversal // of the left subtree and preorder if (!checkInorderPreorderUtil( leftInorderStart, leftInorderEnd, preorder)) return false ; // Check if the left subtree can be // built from the inorder traversal // of the left subtree and preorder else return checkInorderPreorderUtil( rightInorderStart, rightInorderEnd, preorder); } // Function to check for the validation of // inorder and preorder function checkInorderPreorder(pre, inn, n) { for (let i = 0; i < n; i++) inorderIndexMap.set(inn[i], i); preIndex = 0; if (checkInorderPreorderUtil( 0, n - 1, pre )) { return "Yes" ; } else { return "No" ; } } // Driver Code let pre = [ 1, 2, 4, 5, 7, 3, 6, 8 ]; let inn = [ 4, 2, 5, 7, 1, 6, 8, 3 ]; let N = pre.length; document.write(checkInorderPreorder(pre, inn, N)); // This code is contributed by saurabh_jaiswal. </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach : solve this problem is to use a single array for the both preorder and inorder traversals. The key observation is that if the given traversals are valid for a binary tree, then the root of the tree must be the first element in the preorder traversal.
Here’s the implementation of this approach:
C++
#include <iostream> #include <vector> #include <unordered_map> #include <stack> #include <climits> using namespace std; bool GFG( const vector< int >& preorder, const vector< int >& inorder) { // Base case: if the lengths of preorder and // inorder are different, it's not valid if (preorder.size() != inorder.size()) { return false ; } // Create a map to store the index of // each element in the inorder traversal unordered_map< int , int > inorder_map; for ( int i = 0; i < inorder.size(); ++i) { inorder_map[inorder[i]] = i; } // Initialize the stack to simulate the recursive process stack< int > st; int root = INT_MIN; // Iterate through each element in the preorder traversal for ( int val : preorder) { // If the current value in preorder is not in // the inorder traversal, it's not valid if (inorder_map.find(val) == inorder_map.end()) { return false ; } // If the current value is smaller than the root, push it onto the stack if (inorder_map[val] < inorder_map[root]) { st.push(val); } else { // If the current value is greater than the root, pop elements from stack // until we find the parent of the current value while (!st.empty() && inorder_map[val] > inorder_map[st.top()]) { root = st.top(); st.pop(); } // Set the parent of the current value as the root and // push the current value onto the stack st.push(val); } } return true ; } int main() { // Example usage: vector< int > pre1 = {1, 2, 4, 5, 7, 3, 6, 8}; vector< int > in1 = {4, 2, 5, 7, 1, 6, 8, 3}; cout << (GFG(pre1, in1) ? "Yes" : "No" ) << endl; vector< int > pre2 = {1, 2, 69, 5, 7, 3, 6, 8}; vector< int > in2 = {4, 2, 5, 7, 1, 6, 8, 3}; cout << (GFG(pre2, in2) ? "Yes" : "No" ) << endl; return 0; } |
Java
import java.util.*; public class Main { public static boolean isBST(List<Integer> preorder, List<Integer> inorder) { // Base case: if the lengths of preorder and inorder // are different, it's not valid if (preorder.size() != inorder.size()) { return false ; } // Create a map to store the index of each element // in the inorder traversal Map<Integer, Integer> inorderMap = new HashMap<>(); for ( int i = 0 ; i < inorder.size(); ++i) { inorderMap.put(inorder.get(i), i); } // Initialize the stack to simulate the recursive // process Stack<Integer> stack = new Stack<>(); int root = preorder.get( 0 ); // Initialize root to the // first element in preorder // Iterate through each element in the preorder // traversal for ( int val : preorder) { // If the current value in preorder is not in // the inorder traversal, it's not valid if (!inorderMap.containsKey(val)) { return false ; } // Update root if the current value is smaller // than the current root if (inorderMap.get(val) < inorderMap.get(root)) { stack.push(val); } else { // If the current value is greater than the // root, pop elements from stack until we // find the parent of the current value while ( !stack.isEmpty() && inorderMap.get(val) > inorderMap.get(stack.peek())) { root = stack.pop(); } // Set the parent of the current value as // the root and push the current value onto // the stack stack.push(val); } } return true ; } public static void main(String[] args) { // Example usage: List<Integer> pre1 = Arrays.asList( 1 , 2 , 4 , 5 , 7 , 3 , 6 , 8 ); List<Integer> in1 = Arrays.asList( 4 , 2 , 5 , 7 , 1 , 6 , 8 , 3 ); System.out.println(isBST(pre1, in1) ? "Yes" : "No" ); List<Integer> pre2 = Arrays.asList( 1 , 2 , 69 , 5 , 7 , 3 , 6 , 8 ); List<Integer> in2 = Arrays.asList( 4 , 2 , 5 , 7 , 1 , 6 , 8 , 3 ); System.out.println(isBST(pre2, in2) ? "Yes" : "No" ); } } |
Python3
class TreeNode: def __init__( self , val = 0 , left = None , right = None ): self .val = val self .left = left self .right = right def isBST(preorder, inorder): # Base case: if the lengths of preorder and inorder # are different, it's not valid if len (preorder) ! = len (inorder): return False # Create a dictionary to store the index of each element # in the inorder traversal inorder_map = {val: i for i, val in enumerate (inorder)} # Initialize the stack to simulate the recursive process stack = [] root = preorder[ 0 ] # Initialize root to the first element in preorder # Iterate through each element in the preorder traversal for val in preorder: # If the current value in preorder is not in # the inorder traversal, it's not valid if val not in inorder_map: return False # Update root if the current value is smaller # than the current root if inorder_map[val] < inorder_map[root]: stack.append(val) else : # If the current value is greater than the # root, pop elements from stack until we # find the parent of the current value while stack and inorder_map[val] > inorder_map[stack[ - 1 ]]: root = stack.pop() # Set the parent of the current value as # the root and push the current value onto # the stack stack.append(val) return True # Example usage: pre1 = [ 1 , 2 , 4 , 5 , 7 , 3 , 6 , 8 ] in1 = [ 4 , 2 , 5 , 7 , 1 , 6 , 8 , 3 ] print ( "Yes" if isBST(pre1, in1) else "No" ) pre2 = [ 1 , 2 , 69 , 5 , 7 , 3 , 6 , 8 ] in2 = [ 4 , 2 , 5 , 7 , 1 , 6 , 8 , 3 ] print ( "Yes" if isBST(pre2, in2) else "No" ) # This code is contributed by Dwaipayan Bandyopadhyay |
C#
using System; using System.Collections.Generic; class Program { static bool GFG(List< int > preorder, List< int > inorder) { // Base case: if the lengths of preorder and // inorder are different, it's not valid if (preorder.Count != inorder.Count) { return false ; } // Create a map to store the index of // each element in the inorder traversal Dictionary< int , int > inorderMap = new Dictionary< int , int >(); for ( int i = 0; i < inorder.Count; ++i) { inorderMap[inorder[i]] = i; } // Initialize the stack to simulate the recursive process Stack< int > stack = new Stack< int >(); int root = preorder[0]; // Initialize root to the first element in preorder // Iterate through each element in the preorder traversal foreach ( int val in preorder) { // If the current value in preorder is not in // the inorder traversal, it's not valid if (!inorderMap.ContainsKey(val)) { return false ; } // Update root if the current value is smaller than the current root if (inorderMap[val] < inorderMap[root]) { stack.Push(val); } else { // If the current value is greater than the root, pop elements from stack // until we find the parent of the current value while (stack.Count > 0 && inorderMap[val] > inorderMap[stack.Peek()]) { root = stack.Pop(); } // Set the parent of the current value as the root and // push the current value onto the stack stack.Push(val); } } return true ; } static void Main() { // Example usage: List< int > pre1 = new List< int > { 1, 2, 4, 5, 7, 3, 6, 8 }; List< int > in1 = new List< int > { 4, 2, 5, 7, 1, 6, 8, 3 }; Console.WriteLine(GFG(pre1, in1) ? "Yes" : "No" ); List< int > pre2 = new List< int > { 1, 2, 69, 5, 7, 3, 6, 8 }; List< int > in2 = new List< int > { 4, 2, 5, 7, 1, 6, 8, 3 }; Console.WriteLine(GFG(pre2, in2) ? "Yes" : "No" ); } } |
Javascript
function GFG(preorder, inorder) { // Base case: if the lengths of preorder and inorder are different, it's not valid if (preorder.length !== inorder.length) { return false ; } // Create a map to store the index of each element in the inorder traversal const inorderMap = new Map(); inorder.forEach((val, i) => { inorderMap.set(val, i); }); // Initialize the stack to simulate the recursive process const stack = []; let root = Number.MIN_SAFE_INTEGER; // Iterate through each element in the preorder traversal for (const val of preorder) { // If the current value in preorder is not in the inorder traversal, it's not valid if (!inorderMap.has(val)) { return false ; } // If the current value is smaller than the root, push it onto the stack if (inorderMap.get(val) < inorderMap.get(root)) { stack.push(val); } else { // If the current value is greater than the root, pop elements from stack // until we find the parent of the current value while (stack.length > 0 && inorderMap.get(val) > inorderMap.get(stack[stack.length - 1])) { root = stack.pop(); } // Set the parent of the current value as the root and // push the current value onto the stack stack.push(val); } } return true ; } // Example usage: const pre1 = [1, 2, 4, 5, 7, 3, 6, 8]; const in1 = [4, 2, 5, 7, 1, 6, 8, 3]; console.log(GFG(pre1, in1) ? "Yes" : "No" ); const pre2 = [1, 2, 69, 5, 7, 3, 6, 8]; const in2 = [4, 2, 5, 7, 1, 6, 8, 3]; console.log(GFG(pre2, in2) ? "Yes" : "No" ); |
Yes No