Problem

A Cartesian tree with sequence S is a binary tree defined by the following two properties:

  1. It is heap-ordered, so that each parent value is strictly less than that of its children.
  2. An in-order traversal of the tree produces nodes with values that correspond exactly to S.

For example, given the sequence [3, 2, 6, 1, 9], the resulting Cartesian tree would be:

1
2
3
4
5

      1
    /   \   
  2       9
 / \
3   6

Given a sequence S, construct the corresponding Cartesian tree.

Examples

Example 1

1
2
3
4
5
6
7

Input: [3, 2, 6, 1, 9]
Output: Tree with root 1, left subtree contains [3, 2, 6] with root 2, right subtree contains [9]
Explanation:
- Minimum element 1 becomes root (heap property)
- Elements [3, 2, 6] to the left of 1 form left subtree
- Elements [9] to the right of 1 form right subtree
- In-order traversal: 3, 2, 6, 1, 9 matches input sequence

Example 2

1
2
3
4
5
6
7

Input: [1, 2, 3]
Output: Tree with root 1, right child 2, right child of 2 is 3
Explanation:
- 1 is minimum, becomes root
- [2, 3] forms right subtree
- 2 becomes root of right subtree, 3 becomes right child of 2
- In-order: 1, 2, 3

Example 3

1
2
3
4
5
6
7

Input: [3, 2, 1]
Output: Tree with root 1, left child 2, left child of 2 is 3
Explanation:
- 1 is minimum, becomes root
- [3, 2] forms left subtree
- 2 becomes root of left subtree, 3 becomes left child of 2
- In-order: 3, 2, 1

Example 4

1
2
3
4
5

Input: [5]
Output: Single node tree with value 5
Explanation: 
- Only one element, forms root
- No left or right subtrees

Example 5

1
2
3
4
5
6
7

Input: [4, 3, 2, 1, 2, 3, 4]
Output: Tree with root 1, balanced structure maintaining heap and in-order properties
Explanation:
- 1 is minimum at index 3, becomes root
- [4, 3, 2] forms left subtree with root 2
- [2, 3, 4] forms right subtree with root 2
- In-order traversal preserves original sequence

Solution

Method 1 - Divide and Conquer Recursive

Intuition

The key insight is that in a Cartesian tree, the minimum element of any range becomes the root of that subtree. We can recursively apply this property: find the minimum element, make it the root, then recursively build left and right subtrees from the elements to the left and right of the minimum.

Approach

  1. Base case: if the sequence is empty, return null
  2. Find the minimum element and its index in the current range
  3. Create a new tree node with the minimum value as root
  4. Recursively build the left subtree from elements before the minimum index
  5. Recursively build the right subtree from elements after the minimum index
  6. Connect the left and right subtrees to the root
  7. Return the root node

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* buildCartesianTree(vector<int>& nums) {
        return buildHelper(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* buildHelper(vector<int>& nums, int start, int end) {
        if (start > end) return nullptr;
        
        // Find minimum element and its index
        int minIdx = start;
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] < nums[minIdx]) {
                minIdx = i;
            }
        }
        
        // Create root with minimum value
        TreeNode* root = new TreeNode(nums[minIdx]);
        
        // Recursively build left and right subtrees
        root->left = buildHelper(nums, start, minIdx - 1);
        root->right = buildHelper(nums, minIdx + 1, end);
        
        return root;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func buildCartesianTree(nums []int) *TreeNode {
    return buildHelper(nums, 0, len(nums)-1)
}

func buildHelper(nums []int, start, end int) *TreeNode {
    if start > end {
        return nil
    }
    
    // Find minimum element and its index
    minIdx := start
    for i := start + 1; i <= end; i++ {
        if nums[i] < nums[minIdx] {
            minIdx = i
        }
    }
    
    // Create root with minimum value
    root := &TreeNode{Val: nums[minIdx]}
    
    // Recursively build left and right subtrees
    root.Left = buildHelper(nums, start, minIdx-1)
    root.Right = buildHelper(nums, minIdx+1, end)
    
    return root
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode buildCartesianTree(int[] nums) {
        return buildHelper(nums, 0, nums.length - 1);
    }
    
    private TreeNode buildHelper(int[] nums, int start, int end) {
        if (start > end) return null;
        
        // Find minimum element and its index
        int minIdx = start;
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] < nums[minIdx]) {
                minIdx = i;
            }
        }
        
        // Create root with minimum value
        TreeNode root = new TreeNode(nums[minIdx]);
        
        // Recursively build left and right subtrees
        root.left = buildHelper(nums, start, minIdx - 1);
        root.right = buildHelper(nums, minIdx + 1, end);
        
        return root;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def build_cartesian_tree(self, nums: List[int]) -> TreeNode:
        return self._build_helper(nums, 0, len(nums) - 1)
    
    def _build_helper(self, nums: List[int], start: int, end: int) -> TreeNode:
        if start > end:
            return None
        
        # Find minimum element and its index
        min_idx = start
        for i in range(start + 1, end + 1):
            if nums[i] < nums[min_idx]:
                min_idx = i
        
        # Create root with minimum value
        root = TreeNode(nums[min_idx])
        
        # Recursively build left and right subtrees
        root.left = self._build_helper(nums, start, min_idx - 1)
        root.right = self._build_helper(nums, min_idx + 1, end)
        
        return root

Complexity

  • ⏰ Time complexity: O(N²), where N is the length of the sequence. In worst case (sorted array), we scan entire array for minimum at each level
  • 🧺 Space complexity: O(N), for recursion stack depth which can be up to N in worst case

Method 2 - Stack-based Linear Construction

Intuition

We can build the Cartesian tree in linear time using a stack-based approach. The key insight is to process elements from left to right, maintaining a stack of nodes where each node in the stack has a smaller value than the nodes below it. When we encounter a smaller element, we pop nodes from the stack and make them children appropriately.

Approach

  1. Initialize an empty stack to store TreeNode references
  2. For each element in the sequence from left to right:
    • Create a new node with current element
    • While stack is not empty and top element is greater than current:
      • Pop the top node and make it left child of current node
    • If stack is not empty after popping, make current node right child of stack top
    • Push current node to stack
  3. The bottom element of stack is the root of Cartesian tree
  4. Return the root

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    TreeNode* buildCartesianTreeLinear(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        
        stack<TreeNode*> st;
        
        for (int num : nums) {
            TreeNode* node = new TreeNode(num);
            TreeNode* lastPopped = nullptr;
            
            // Pop nodes greater than current
            while (!st.empty() && st.top()->val > num) {
                lastPopped = st.top();
                st.pop();
            }
            
            // Make last popped node as left child
            if (lastPopped) {
                node->left = lastPopped;
            }
            
            // Make current node as right child of stack top
            if (!st.empty()) {
                st.top()->right = node;
            }
            
            st.push(node);
        }
        
        // Find root (bottom of stack)
        TreeNode* root = nullptr;
        while (!st.empty()) {
            root = st.top();
            st.pop();
        }
        
        return root;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func buildCartesianTreeLinear(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    
    var stack []*TreeNode
    
    for _, num := range nums {
        node := &TreeNode{Val: num}
        var lastPopped *TreeNode
        
        // Pop nodes greater than current
        for len(stack) > 0 && stack[len(stack)-1].Val > num {
            lastPopped = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        
        // Make last popped node as left child
        if lastPopped != nil {
            node.Left = lastPopped
        }
        
        // Make current node as right child of stack top
        if len(stack) > 0 {
            stack[len(stack)-1].Right = node
        }
        
        stack = append(stack, node)
    }
    
    // Find root (bottom of stack)
    var root *TreeNode
    for len(stack) > 0 {
        root = stack[0]
        break
    }
    
    return root
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public TreeNode buildCartesianTreeLinear(int[] nums) {
        if (nums.length == 0) return null;
        
        Stack<TreeNode> stack = new Stack<>();
        
        for (int num : nums) {
            TreeNode node = new TreeNode(num);
            TreeNode lastPopped = null;
            
            // Pop nodes greater than current
            while (!stack.isEmpty() && stack.peek().val > num) {
                lastPopped = stack.pop();
            }
            
            // Make last popped node as left child
            if (lastPopped != null) {
                node.left = lastPopped;
            }
            
            // Make current node as right child of stack top
            if (!stack.isEmpty()) {
                stack.peek().right = node;
            }
            
            stack.push(node);
        }
        
        // Find root (bottom of stack)
        TreeNode root = null;
        while (!stack.isEmpty()) {
            root = stack.pop();
        }
        
        return root;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def build_cartesian_tree_linear(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        
        stack = []
        
        for num in nums:
            node = TreeNode(num)
            last_popped = None
            
            # Pop nodes greater than current
            while stack and stack[-1].val > num:
                last_popped = stack.pop()
            
            # Make last popped node as left child
            if last_popped:
                node.left = last_popped
            
            # Make current node as right child of stack top
            if stack:
                stack[-1].right = node
            
            stack.append(node)
        
        # Find root (bottom of stack)
        root = None
        while stack:
            root = stack.pop()
        
        return root

Complexity

  • ⏰ Time complexity: O(N), where N is the length of the sequence. Each element is pushed and popped at most once
  • 🧺 Space complexity: O(N), for the stack which can contain up to N nodes

Method 3 - Segment Tree Based Construction

Intuition

We can use a segment tree approach where we preprocess the array to quickly find range minimum queries (RMQ). This allows us to find the minimum element in any range in O(log N) time, leading to better average performance for the divide and conquer approach.

Approach

  1. Build a segment tree for range minimum queries in O(N log N) time
  2. Use divide and conquer approach but leverage segment tree for O(log N) minimum finding
  3. For each recursive call, query segment tree to find minimum in current range
  4. Recursively build left and right subtrees based on minimum position
  5. This reduces the time complexity of finding minimum from O(N) to O(log N)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

class Solution:
    def build_cartesian_tree_segment(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        
        n = len(nums)
        # Build segment tree for RMQ
        seg_tree = [0] * (4 * n)
        self._build_segment_tree(nums, seg_tree, 0, 0, n - 1)
        
        return self._build_with_rmq(nums, seg_tree, 0, n - 1, 0, n - 1)
    
    def _build_segment_tree(self, nums: List[int], tree: List[int], 
                           node: int, start: int, end: int) -> None:
        if start == end:
            tree[node] = start
        else:
            mid = (start + end) // 2
            self._build_segment_tree(nums, tree, 2 * node + 1, start, mid)
            self._build_segment_tree(nums, tree, 2 * node + 2, mid + 1, end)
            
            left_idx = tree[2 * node + 1]
            right_idx = tree[2 * node + 2]
            tree[node] = left_idx if nums[left_idx] <= nums[right_idx] else right_idx
    
    def _query_rmq(self, nums: List[int], tree: List[int], node: int, 
                   start: int, end: int, l: int, r: int) -> int:
        if r < start or end < l:
            return -1
        
        if l <= start and end <= r:
            return tree[node]
        
        mid = (start + end) // 2
        left_idx = self._query_rmq(nums, tree, 2 * node + 1, start, mid, l, r)
        right_idx = self._query_rmq(nums, tree, 2 * node + 2, mid + 1, end, l, r)
        
        if left_idx == -1:
            return right_idx
        if right_idx == -1:
            return left_idx
        
        return left_idx if nums[left_idx] <= nums[right_idx] else right_idx
    
    def _build_with_rmq(self, nums: List[int], tree: List[int], 
                        tree_start: int, tree_end: int, start: int, end: int) -> TreeNode:
        if start > end:
            return None
        
        # Find minimum using segment tree
        min_idx = self._query_rmq(nums, tree, 0, tree_start, tree_end, start, end)
        root = TreeNode(nums[min_idx])
        
        # Recursively build subtrees
        root.left = self._build_with_rmq(nums, tree, tree_start, tree_end, start, min_idx - 1)
        root.right = self._build_with_rmq(nums, tree, tree_start, tree_end, min_idx + 1, end)
        
        return root

Complexity

  • ⏰ Time complexity: O(N log N), where N is the length of the sequence. Building segment tree takes O(N log N) and each query takes O(log N)
  • 🧺 Space complexity: O(N), for the segment tree and recursion stack

Notes

  • Method 1 is intuitive but has O(N²) worst-case time complexity
  • Method 2 is optimal with O(N) time complexity and is the preferred approach
  • Method 3 provides a middle ground with O(N log N) complexity but more complex implementation
  • The Cartesian tree is useful in applications like range minimum queries and treaps
  • The stack-based approach exploits the property that we can build the tree in a single left-to-right pass
  • In-order traversal of the constructed tree always yields the original sequence