> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/inorder-traversal-of-cartesian-tree.md).

# Inorder Traversal of Cartesian Tree

Given an inorder traversal of a cartesian tree, construct the tree.

> **Cartesian tree** : is a heap ordered binary tree, where the root is greater than all the elements in the subtree. 

> **Note:** You may assume that duplicates do not exist in the tree. 

**Example :**

```
Input : [1 2 3]

Return :   
          3
         /
        2
       /
      1
```

```java
public class Solution {
    // Naive solution ->
    // We know the root is the highest element in the whole array (O(N))
    // Now for all the subtrees, we will be searching the biggest node
    // Complexity will be O(N*Height) worst case -> (N*N), because we will be doing
    // an overall search of N at every level of the tree

    // Now how can we find the max element in a range ? -> SEGMENT Tree
    // So using segment trees, worst case complexity will be O(NlogN)
    // Basic of segment tree - https://www.geeksforgeeks.org/segment-tree-data-structure/
    static class SegmentTree {
        // Tree stores max element & it's index
        int tree[][], arr[];

        SegmentTree(int[] arr) {
            this.arr = arr;
            int n = arr.length;
            tree = new int[4 * n][];
            buildTree(0, n - 1, 1);
        }

        public void buildTree(int start, int end, int index) {
            if (start == end) {
                tree[index] = new int[] { arr[start], start };
                return;
            }
            int mid = start + (end - start) / 2;
            buildTree(start, mid, 2 * index);
            buildTree(mid + 1, end, 2 * index + 1);
            if (tree[2 * index][0] > tree[2 * index + 1][0])
                tree[index] = tree[2 * index];
            else
                tree[index] = tree[2 * index + 1];
        }

        public int findMax(int L, int R) {
            int[] ans = query(0, arr.length - 1, 1, L, R);
            return ans[1];
        }

        public int[] query(int start, int end, int index, int L, int R) {
            if (start > R || end < L)
                return new int[] { Integer.MIN_VALUE, -1 };
            else if (start >= L && end <= R)
                return tree[index];
            int mid = start + (end - start) / 2;
            int[] leftMax = query(start, mid, 2 * index, L, R);
            int[] rightMax = query(mid + 1, end, 2 * index + 1, L, R);
            if (leftMax[0] > rightMax[0])
                return leftMax;
            return rightMax;
        }
    }

    SegmentTree segTree;

    public TreeNode buildTree(int[] A) {
        segTree = new SegmentTree(A);
        return helper(A, 0, A.length - 1);
    }

    public TreeNode helper(int[] A, int start, int end) {
        if (start > end)
            return null;
        // O(logN)
        int rootIndex = segTree.findMax(start, end);
        TreeNode root = new TreeNode(A[rootIndex]);
        root.left = helper(A, start, rootIndex - 1);
        root.right = helper(A, rootIndex + 1, end);
        return root;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/trees/inorder-traversal-of-cartesian-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.