Given 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 notbool 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 preorderstring 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 Codeint 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 notimport 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 preorderstatic 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 Codepublic 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 notdef 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 preorderdef 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 Codeif __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 notusing 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 preorderstatic 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 Codepublic 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 approachlet 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 preorderfunction 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> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
