data-structurestreebinary-search-tree# Can we construct BST from inorder sequence?

We can construct a Binary Search Tree (BST) from a preOrder or postOrder sequence. But can we construct a BST from an inorder sequence alone? I think it is not possible to construct a BST using an inOrder sequence, as we cannot find its root element.

Solution

You are correct. Two different Binary Search Trees can have the same inorder sequence, so you wouldn't know which one to pick. If however, it would be OK to pick any BST that has that inorder sequence, then it is possible.

But I guess your question is about *reconstructing* the *same* BST as the tree from which the inorder sequence was derived. *That* is not possible: by converting a BST to an inorder sequence, you lose information. Even if you would be given the root as *additional* information, you would not generally be able to do it. In fact, the shape of the BST can be anything possible with the given number of nodes.

The smallest example is inorder [1, 2]. It can represent both of these trees:

```
2 1
/ \
1 2
```

If in this case you were given the root as extra information, then it would of course be possible to derive the BST from it.

The next smallest example: [1, 2, 3]. These trees all have that as inorder sequence:

```
3 2 1
/ / \ \
2 1 3 2
/ \
1 3
```

Also here it is true that if you were given the root as extra information, you would be able to know which of the three BSTs was the right one.

But once we get to larger trees, we would not always be able to know the right BST, even if we were given the root.

Note also that a BST does not *have* to be optimally balanced. But even if we would only consider optimally balanced BSTs, an inorder sequence does not uniquely define the tree. The example with 2 nodes above is already proof of that. But let's look at four nodes for which the inorder sequence would be [1, 2, 3, 4]. The most-balanced trees with that inorder sequence are:

```
3 3 2 2
/ \ / \ / \ / \
2 4 1 4 1 4 1 3
/ \ / \
1 2 3 4
```

And here we also see that if we were given the root of the optimally balanced BST, there still would be two possibilities left.

- I am trying to reverse the stack using recursion. What is being passed in function fun()? s is an object of class stack
- Modify 2d array to create nested datasets when specific key is encountered
- JS - recursive function on multidimensional array to filter out only "checked" items (and its parents if a child is selected)
- Comparing two similar objects (holding same keys) and returning key value pairs that are different
- Linked List Replacement Function with Head, Tail, and Size Management
- Efficient Array Storage for Binary Tree
- How to render data and initialize an UI event handling upon this data after the data has been loaded by an asynchronous API call?
- Hackerrank Repeated String infinite loop problem
- Using asterisk and spaces print the letter R [ 21*20]
- Split a collection into `n` parts with LINQ?
- How can I enhance the time complexity of arranging bricks into stacks based on specific conditions?
- List-like data-structure with O(1) access in practice but O(N) access for huge sizes; What is it?
- Octree implementation in Rust: why is the insert function duplicating insertions and how could I go about fixing this?
- how to traverse an NxN grid diagonally
- Name of binary data structures that contain fixed-length components?
- Insert after specific element in LinkedList java
- inserting in binary tree doesn't work using java
- Generate simple URL patterns from a list of examples
- Explain time complexity of permutations using the mathematical expression
- segfault with no reason in sight while implementing a dsu in c (probably a silly mistake)
- Why AddAfter() has constant time?
- 2D peak finding algorithm in O(n) worst case time?
- C# Multiway Linked List
- Find Elements occurring odd number of times in a list
- Difference between back tracking and dynamic programming
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Difference between vertices and edges [Graphs, Algorithm and DS]
- How to find the time comlexity when comparing sublists?
- My quicksort algorithm is very slow so what can I do to make it faster?