Find all possible binary trees with given Inorder Traversal - GeeksforGeeks


Find all possible binary trees with given Inorder Traversal - GeeksforGeeks
Given an array that represents Inorder Traversal, find all possible Binary Trees with the given Inorder traversal and print their preorder traversals.
Let given inorder traversal be in[]. In the given traversal, all nodes in left subtree of in[i] must appear before it and in right subtree must appear after it. So when we consider in[i] as root, all elements from in[0] to in[i-1] will be in left subtree and in[i+1] to n-1 will be in right subtree. If in[0] to in[i-1] can form xdifferent trees and in[i+1] to in[n-1] can from y different trees then we will have x*y total trees when in[i] as root. So we simply iterate from 0 to n-1 for root. For every node in[i], recursively find different left and right subtrees. If we take a closer look, we can notice that the count is basically n’th Catalan number. We have discussed different approaches to find n’th Catalan number here.
The idea is to maintain a list of roots of all Binary Trees. Recursively construct all possible left and right subtrees. Create a tree for every pair of left and right subtree and add the tree to list. Below is detailed algorithm.
1) Initialize list of Binary Trees as empty.  
2) For every element in[i] where i varies from 0 to n-1,
    do following
......a)  Create a new node with key as 'arr[i]', 
          let this node be 'node'
......b)  Recursively construct list of all left subtrees.
......c)  Recursively construct list of all right subtrees.
3) Iterate for all left subtrees
   a) For current leftsubtree, iterate for all right subtrees
        Add current left and right subtrees to 'node' and add
        'node' to list.
class Node {
    int data;
    Node left, right;
    public Node(int item) {
        data = item;
        left = null;
        right = null;
    }
}
/* Class to print Level Order Traversal */
class BinaryTree {
    Node root;
    // A utility function to do preorder traversal of BST
    void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + " "    );
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    // Function for constructing all possible trees with
    // given inorder traversal stored in an array from
    // arr[start] to arr[end]. This function returns a
    // vector of trees.
    Vector<Node> getTrees(int arr[], int start, int end) {
        // List to store all possible trees
        Vector<Node> trees= new Vector<Node>();
        /* if start > end then subtree will be empty so
         returning NULL in the list */
        if (start > end) {
            trees.add(null);
            return trees;
        }
        /* Iterating through all values from start to end
         for constructing left and right subtree
         recursively */
        for (int i = start; i <= end; i++) {
            /* Constructing left subtree */
            Vector<Node> ltrees = getTrees(arr, start, i - 1);
             
            /* Constructing right subtree */
            Vector<Node> rtrees = getTrees(arr, i + 1, end);
            /* Now looping through all left and right subtrees
             and connecting them to ith root below */
            for (int j = 0; j < ltrees.size(); j++) {
                for (int k = 0; k < rtrees.size(); k++) {
                    // Making arr[i] as root
                    Node node = new Node(arr[i]);
                    // Connecting left subtree
                    node.left = ltrees.get(j);
                    // Connecting right subtree
                    node.right = rtrees.get(k);
                    // Adding this tree to list
                    trees.add(node);
                }
            }
        }
        return trees;
    }

class Node:
    # Utility to create a new node
    def __init__(self , item):
        self.key = item
        self.left = None
        self.right = None
# A utility function to do preorder traversal of BST
def preorder(root):
    if root is not None:
        print root.key,
        preorder(root.left)
        preorder(root.right)
# Function for constructing all possible trees with
# given inorder traversal stored in an array from
# arr[start] to arr[end]. This function returns a
# vector of trees.
def getTrees(arr , start , end):
    # List to store all possible trees
    trees = []
     
    """ if start > end then subtree will be empty so
    returning NULL in the list """
    if start > end :
        trees.append(None)
        return trees
     
    """ Iterating through all values from start to end
        for constructing left and right subtree
        recursively """
    for i in range(start , end+1):
        # Constructing left subtree
        ltrees = getTrees(arr , start , i-1)
         
        # Constructing right subtree
        rtrees = getTrees(arr , i+1 , end)
         
        """ Looping through all left and right subtrees
        and connecting to ith root below"""
        for j in ltrees :
            for k in rtrees :
                # Making arr[i]  as root
                node  = Node(arr[i])
     
                # Connecting left subtree
                node.left =
                # Connecting right subtree
                node.right = k
                # Adding this tree to list
                trees.append(node)
    return trees
# Driver program to test above function
inp = [4 , 5, 7]
n = len(inp)
trees = getTrees(inp , 0 , n-1)
print "Preorder traversals of different possible\
 Binary Trees are "
for i in trees :
    preorder(i);
    print ""

Related: Construct all possible BSTs for keys 1 to N
Read full article from Find all possible binary trees with given Inorder Traversal - GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts