Open In App

Cartesian Tree

Last Updated : 20 Jan, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

A Cartesian tree is a tree data structure created from a set of data that obeys the  following structural invariants:
 

  1. The tree obeys in the min (or max) heap property – each node is less (or greater) than its children.
  2. An inorder traversal of the nodes yields the values in the same order in which they appear in the initial sequence.

Suppose we have an input array- {5,10,40,30,28}. Then the max-heap Cartesian Tree would be.
 

cartesianTree0

A min-heap Cartesian Tree of the above input array will be- 
 

cartesianTree1

Note: 
 

  1. Cartesian Tree is not a height-balanced tree.
  2. Cartesian tree of a sequence of distinct numbers is always unique.

Cartesian tree of a sequence of distinct numbers is always unique. 
We will prove this using induction. As a base case, empty tree is always unique. For the inductive case, assume that for all trees containing n’ < n elements, there is a unique Cartesian tree for each sequence of n’ nodes. Now take any sequence of n elements. Because a Cartesian tree is a min-heap, the smallest element of the sequence must be the root of the Cartesian tree. Because an inorder traversal of the elements must yield the input sequence, we know that all nodes to the left of the min element must be in its left subtree and similarly for the nodes to the right. Since the left and right subtree are both Cartesian trees with at most n-1 elements in them (since the min element is at the root), by the induction hypothesis there is a unique Cartesian tree that could be the left or right subtree. Since all our decisions were forced, we end up with a unique tree, completing the induction.
How to construct Cartesian Tree? 
A O(n2) solution for construction of Cartesian Tree is discussed here (Note that the above program here constructs the “special binary tree” (which is nothing but a Cartesian tree)
A O(nlogn) Algorithm : 
It’s possible to build a Cartesian tree from a sequence of data in O(NlogN) time on average. Beginning with the empty tree,
Scan the given sequence from left to right adding new nodes as follows: 
 

  1. Position the node as the right child of the rightmost node.
  2. Scan upward from the node’s parent up to the root of the tree until a node is found whose value is greater than the current value.
  3. If such a node is found, set its right child to be the new node, and set the new node’s left child to be the previous right child.
  4. If no such node is found, set the new child to be the root, and set the new node’s left child to be the previous tree.

 

CPP




// A O(n) C++ program to construct cartesian tree
// from a given array
#include<bits/stdc++.h>
 
/* A binary tree node has data, pointer to left
   child and a pointer to right child */
struct Node
{
    int data;
    Node *left, *right;
};
 
/* This function is here just to test buildTree() */
void printInorder (Node* node)
{
    if (node == NULL)
        return;
    printInorder (node->left);
    cout << node->data << " ";
    printInorder (node->right);
}
 
// Recursively construct subtree under given root using
// leftChild[] and rightchild
Node * buildCartesianTreeUtil (int root, int arr[],
          int parent[], int leftchild[], int rightchild[])
{
    if (root == -1)
        return NULL;
 
    // Create a new node with root's data
    Node *temp = new Node;
    temp->data = arr[root] ;
 
    // Recursively construct left and right subtrees
    temp->left = buildCartesianTreeUtil( leftchild[root],
                    arr, parent, leftchild, rightchild );
    temp->right = buildCartesianTreeUtil( rightchild[root],
                    arr, parent, leftchild, rightchild );
 
    return temp ;
}
 
// A function to create the Cartesian Tree in O(N) time
Node * buildCartesianTree (int arr[], int n)
{
    // Arrays to hold the index of parent, left-child,
    // right-child of each number in the input array
    int parent[n],leftchild[n],rightchild[n];
 
    // Initialize all array values as -1
    memset(parent, -1, sizeof(parent));
    memset(leftchild, -1, sizeof(leftchild));
    memset(rightchild, -1, sizeof(rightchild));
 
    // 'root' and 'last' stores the index of the root and the
    // last processed of the Cartesian Tree.
    // Initially we take root of the Cartesian Tree as the
    // first element of the input array. This can change
    // according to the algorithm
    int root = 0, last;
 
    // Starting from the second element of the input array
    // to the last on scan across the elements, adding them
    // one at a time.
    for (int i=1; i<=n-1; i++)
    {
        last = i-1;
        rightchild[i] = -1;
 
        // Scan upward from the node's parent up to
        // the root of the tree until a node is found
        // whose value is greater than the current one
        // This is the same as Step 2 mentioned in the
        // algorithm
        while (arr[last] <= arr[i] && last != root)
            last = parent[last];
 
        // arr[i] is the largest element yet; make it
        // new root
        if (arr[last] <= arr[i])
        {
            parent[root] = i;
            leftchild[i] = root;
            root = i;
        }
 
        // Just insert it
        else if (rightchild[last] == -1)
        {
            rightchild[last] = i;
            parent[i] = last;
            leftchild[i] = -1;
        }
 
        // Reconfigure links
        else
        {
            parent[rightchild[last]] = i;
            leftchild[i] = rightchild[last];
            rightchild[last] = i;
            parent[i] = last;
        }
 
    }
 
    // Since the root of the Cartesian Tree has no
    // parent, so we assign it -1
    parent[root] = -1;
 
    return (buildCartesianTreeUtil (root, arr, parent,
                                    leftchild, rightchild));
}
 
/* Driver program to test above functions */
int main()
{
    /* Assume that inorder traversal of following tree
       is given
         40
       /   \
      10     30
     /         \
    5          28 */
 
    int arr[] = {5, 10, 40, 30, 28};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    Node *root = buildCartesianTree(arr, n);
 
    /* Let us test the built tree by printing Inorder
       traversal */
    printf("Inorder traversal of the constructed tree : \n");
    printInorder(root);
 
    return(0);
}


Java




// A O(n) Java program to construct cartesian tree
// from a given array
 
/* A binary tree node has data, pointer to left
child and a pointer to right child */
class GFG
{
static class Node
{
    int data;
    Node left, right;
};
 
/* This function is here just to test buildTree() */
static void printInorder (Node node)
{
    if (node == null)
        return;
    printInorder (node.left);
    System.out.print(node.data + " ");
    printInorder (node.right);
}
 
// Recursively construct subtree under given root using
// leftChild[] and rightchild
static Node buildCartesianTreeUtil (int root, int arr[],
        int parent[], int leftchild[], int rightchild[])
{
    if (root == -1)
        return null;
 
    // Create a new node with root's data
    Node temp = new Node();
    temp.data = arr[root] ;
 
    // Recursively construct left and right subtrees
    temp.left = buildCartesianTreeUtil( leftchild[root],
                    arr, parent, leftchild, rightchild );
    temp.right = buildCartesianTreeUtil( rightchild[root],
                    arr, parent, leftchild, rightchild );
 
    return temp ;
}
 
// A function to create the Cartesian Tree in O(N) time
static Node buildCartesianTree (int arr[], int n)
{
    // Arrays to hold the index of parent, left-child,
    // right-child of each number in the input array
    int []parent = new int[n];
    int []leftchild = new int[n];
    int []rightchild = new int[n];
 
    // Initialize all array values as -1
    memset(parent, -1);
    memset(leftchild, -1);
    memset(rightchild, -1);
 
    // 'root' and 'last' stores the index of the root and the
    // last processed of the Cartesian Tree.
    // Initially we take root of the Cartesian Tree as the
    // first element of the input array. This can change
    // according to the algorithm
    int root = 0, last;
 
    // Starting from the second element of the input array
    // to the last on scan across the elements, adding them
    // one at a time.
    for (int i = 1; i <= n - 1; i++)
    {
        last = i - 1;
        rightchild[i] = -1;
 
        // Scan upward from the node's parent up to
        // the root of the tree until a node is found
        // whose value is greater than the current one
        // This is the same as Step 2 mentioned in the
        // algorithm
        while (arr[last] <= arr[i] && last != root)
            last = parent[last];
 
        // arr[i] is the largest element yet; make it
        // new root
        if (arr[last] <= arr[i])
        {
            parent[root] = i;
            leftchild[i] = root;
            root = i;
        }
 
        // Just insert it
        else if (rightchild[last] == -1)
        {
            rightchild[last] = i;
            parent[i] = last;
            leftchild[i] = -1;
        }
 
        // Reconfigure links
        else
        {
            parent[rightchild[last]] = i;
            leftchild[i] = rightchild[last];
            rightchild[last] = i;
            parent[i] = last;
        }
 
    }
 
    // Since the root of the Cartesian Tree has no
    // parent, so we assign it -1
    parent[root] = -1;
 
    return (buildCartesianTreeUtil (root, arr, parent,
                                    leftchild, rightchild));
}
 
static void memset(int[] arr, int value)
{
    for (int i = 0; i < arr.length; i++)
    {
        arr[i] = value;
    }
     
}
 
/* Driver code */
public static void main(String[] args)
{
    /* Assume that inorder traversal of following tree
    is given
        40
    / \
    10     30
    /         \
    5         28 */
 
    int arr[] = {5, 10, 40, 30, 28};
    int n = arr.length;
 
    Node root = buildCartesianTree(arr, n);
 
    /* Let us test the built tree by printing Inorder
    traversal */
    System.out.printf("Inorder traversal of the" +
                        " constructed tree : \n");
    printInorder(root);
}
}
 
// This code is contributed by PrinciRaj1992


Python3




# A O(n) python program to construct cartesian tree
# from a given array
 
# Define a Node class for the binary tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Function to print the inorder traversal of the tree
def printInorder(node):
    if node is None:
        return
    printInorder(node.left)
    print(node.data, end=" ")
    printInorder(node.right)
 
# Recursive function to construct the Cartesian tree
def buildCartesianTreeUtil(root, arr, parent, leftchild, rightchild):
    # If the root index is -1, return None
    if root == -1:
        return None
    # Create a new node with the root's data
    temp = Node(arr[root])
    # Recursively construct the left and right subtrees
    temp.left = buildCartesianTreeUtil(leftchild[root], arr, parent, leftchild, rightchild)
    temp.right = buildCartesianTreeUtil(rightchild[root], arr, parent, leftchild, rightchild)
    # Return the constructed node
    return temp
 
# Function to construct the Cartesian tree
def buildCartesianTree(arr):
    n = len(arr)
    # Initialize arrays for parent, left child, and right child
    parent = [-1]*n
    leftchild = [-1]*n
    rightchild = [-1]*n
 
    # Set the root of the tree to be the first element of the input array
    root = 0
    last = None
 
    # Iterate through the input array, adding each element to the tree
    for i in range(1, n):
        last = i-1
        rightchild[i] = -1
        # Scan upward from the element's parent until a node is found whose value is greater than the current one
        while last != root and arr[last] <= arr[i]:
            last = parent[last]
        # If the element is the largest so far, make it the new root
        if arr[last] <= arr[i]:
            parent[root] = i
            leftchild[i] = root
            root = i
        # If there is no right child for the last node, insert the element as the right child
        elif rightchild[last] == -1:
            rightchild[last] = i
            parent[i] = last
            leftchild[i] = -1
        # Else, reconfigure the links to insert the element as the right child
        else:
            parent[rightchild[last]] = i
            leftchild[i] = rightchild[last]
            rightchild[last] = i
            parent[i] = last
 
    # Set the root of the tree to have no parent
    parent[root] = -1
    # Return the constructed tree
    return buildCartesianTreeUtil(root, arr, parent, leftchild, rightchild)
 
# Driver program to test above functions
if __name__ == '__main__':
    arr = [5, 10, 40, 30, 28]
    root = buildCartesianTree(arr)
    print('Inorder traversal of the constructed tree :')
    printInorder(root)


C#




// A O(n) C# program to construct cartesian tree
// from a given array
 
/* A binary tree node has data, pointer to left
child and a pointer to right child */
using System;
 
class GFG
{
     
class Node
{
    public int data;
    public Node left, right;
};
 
/* This function is here just to test buildTree() */
static void printInorder (Node node)
{
    if (node == null)
        return;
    printInorder (node.left);
    Console.Write(node.data + " ");
    printInorder (node.right);
}
 
// Recursively construct subtree under given root using
// leftChild[] and rightchild
static Node buildCartesianTreeUtil (int root, int []arr,
        int []parent, int []leftchild, int []rightchild)
{
    if (root == -1)
        return null;
 
    // Create a new node with root's data
    Node temp = new Node();
    temp.data = arr[root] ;
 
    // Recursively construct left and right subtrees
    temp.left = buildCartesianTreeUtil( leftchild[root],
                    arr, parent, leftchild, rightchild );
    temp.right = buildCartesianTreeUtil( rightchild[root],
                    arr, parent, leftchild, rightchild );
 
    return temp ;
}
 
// A function to create the Cartesian Tree in O(N) time
static Node buildCartesianTree (int []arr, int n)
{
    // Arrays to hold the index of parent, left-child,
    // right-child of each number in the input array
    int []parent = new int[n];
    int []leftchild = new int[n];
    int []rightchild = new int[n];
 
    // Initialize all array values as -1
    memset(parent, -1);
    memset(leftchild, -1);
    memset(rightchild, -1);
 
    // 'root' and 'last' stores the index of the root and the
    // last processed of the Cartesian Tree.
    // Initially we take root of the Cartesian Tree as the
    // first element of the input array. This can change
    // according to the algorithm
    int root = 0, last;
 
    // Starting from the second element of the input array
    // to the last on scan across the elements, adding them
    // one at a time.
    for (int i = 1; i <= n - 1; i++)
    {
        last = i - 1;
        rightchild[i] = -1;
 
        // Scan upward from the node's parent up to
        // the root of the tree until a node is found
        // whose value is greater than the current one
        // This is the same as Step 2 mentioned in the
        // algorithm
        while (arr[last] <= arr[i] && last != root)
            last = parent[last];
 
        // arr[i] is the largest element yet; make it
        // new root
        if (arr[last] <= arr[i])
        {
            parent[root] = i;
            leftchild[i] = root;
            root = i;
        }
 
        // Just insert it
        else if (rightchild[last] == -1)
        {
            rightchild[last] = i;
            parent[i] = last;
            leftchild[i] = -1;
        }
 
        // Reconfigure links
        else
        {
            parent[rightchild[last]] = i;
            leftchild[i] = rightchild[last];
            rightchild[last] = i;
            parent[i] = last;
        }
 
    }
 
    // Since the root of the Cartesian Tree has no
    // parent, so we assign it -1
    parent[root] = -1;
 
    return (buildCartesianTreeUtil (root, arr, parent,
                                    leftchild, rightchild));
}
 
static void memset(int[] arr, int value)
{
    for (int i = 0; i < arr.Length; i++)
    {
        arr[i] = value;
    }
     
}
 
/* Driver code */
public static void Main(String[] args)
{
    /* Assume that inorder traversal of following tree
    is given
        40
    / \
    10     30
    /         \
    5         28 */
 
    int []arr = {5, 10, 40, 30, 28};
    int n = arr.Length;
 
    Node root = buildCartesianTree(arr, n);
 
    /* Let us test the built tree by printing Inorder
    traversal */
    Console.Write("Inorder traversal of the" +
                        " constructed tree : \n");
    printInorder(root);
}
}
 
// This code is contributed by 29AjayKumar


Javascript




<script>
// A O(n) Javascript program to construct cartesian tree
// from a given array
 
/* A binary tree node has data, pointer to left
child and a pointer to right child */
class Node
{
    constructor(data)
    {
        this.data=data;
        this.left=this.right=null;
    }
}
 
/* This function is here just to test buildTree() */
function printInorder (node)
{
    if (node == null)
        return;
    printInorder (node.left);
    document.write(node.data + " ");
    printInorder (node.right);
}
 
// Recursively construct subtree under given root using
// leftChild[] and rightchild
function buildCartesianTreeUtil(root,arr,parent,leftchild,rightchild)
{
     if (root == -1)
        return null;
   
    // Create a new node with root's data
    let temp = new Node();
    temp.data = arr[root] ;
   
    // Recursively construct left and right subtrees
    temp.left = buildCartesianTreeUtil( leftchild[root],
                    arr, parent, leftchild, rightchild );
    temp.right = buildCartesianTreeUtil( rightchild[root],
                    arr, parent, leftchild, rightchild );
   
    return temp ;
}
 
// A function to create the Cartesian Tree in O(N) time
function buildCartesianTree (arr,n)
{
    // Arrays to hold the index of parent, left-child,
    // right-child of each number in the input array
    let parent = new Array(n);
    let leftchild = new Array(n);
    let rightchild = new Array(n);
   
    // Initialize all array values as -1
    memset(parent, -1);
    memset(leftchild, -1);
    memset(rightchild, -1);
   
    // 'root' and 'last' stores the index of the root and the
    // last processed of the Cartesian Tree.
    // Initially we take root of the Cartesian Tree as the
    // first element of the input array. This can change
    // according to the algorithm
    let root = 0, last;
   
    // Starting from the second element of the input array
    // to the last on scan across the elements, adding them
    // one at a time.
    for (let i = 1; i <= n - 1; i++)
    {
        last = i - 1;
        rightchild[i] = -1;
   
        // Scan upward from the node's parent up to
        // the root of the tree until a node is found
        // whose value is greater than the current one
        // This is the same as Step 2 mentioned in the
        // algorithm
        while (arr[last] <= arr[i] && last != root)
            last = parent[last];
   
        // arr[i] is the largest element yet; make it
        // new root
        if (arr[last] <= arr[i])
        {
            parent[root] = i;
            leftchild[i] = root;
            root = i;
        }
   
        // Just insert it
        else if (rightchild[last] == -1)
        {
            rightchild[last] = i;
            parent[i] = last;
            leftchild[i] = -1;
        }
   
        // Reconfigure links
        else
        {
            parent[rightchild[last]] = i;
            leftchild[i] = rightchild[last];
            rightchild[last] = i;
            parent[i] = last;
        }
   
    }
   
    // Since the root of the Cartesian Tree has no
    // parent, so we assign it -1
    parent[root] = -1;
   
    return (buildCartesianTreeUtil (root, arr, parent,
                                    leftchild, rightchild));
}
 
function memset(arr,value)
{
    for (let i = 0; i < arr.length; i++)
    {
        arr[i] = value;
    }
}
 
/* Driver code */
/* Assume that inorder traversal of following tree
    is given
        40
    / \
    10     30
    /         \
    5         28 */
 
let arr = [5, 10, 40, 30, 28];
let n = arr.length;
 
let root = buildCartesianTree(arr, n);
 
/* Let us test the built tree by printing Inorder
    traversal */
document.write("Inorder traversal of the" +
                  " constructed tree : <br>");
printInorder(root);
         
// This code is contributed by rag2127
</script>


Output: 
 

Inorder traversal of the constructed tree :
5 10 40 30 28

Time Complexity : 
At first look, the code seems to be taking O(n2) time as there are two loop in buildCartesianTree(). But actually, it takes O(NlogN) time in average and O(n^2) for sorted preorder traversal.
Auxiliary Space: 
We declare a structure for every node as well as three extra arrays- leftchild[], rightchild[], parent[] to hold the indices of left-child, right-child, parent of each value in the input array. Hence the overall O(4*n) = O(n) extra space.
Application of Cartesian Tree 
 

  • Cartesian Tree Sorting
  • A range minimum query on a sequence is equivalent to a lowest common ancestor query on the sequence’s Cartesian tree. Hence, RMQ may be reduced to LCA using the sequence’s Cartesian tree.
  • Treap, a balanced binary search tree structure, is a Cartesian tree of (key,priority) pairs; it is heap-ordered according to the priority values, and an inorder traversal gives the keys in sorted order.
  • Suffix tree of a string may be constructed from the suffix array and the longest common prefix array. The first step is to compute the Cartesian tree of the longest common prefix array.

References: 
http://wcipeg.com/wiki/Cartesian_tree

 



Similar Reads

Cartesian tree from inorder traversal | Segment Tree
Given an in-order traversal of a cartesian tree, the task is to build the entire tree from it. Examples: Input: arr[] = {1, 5, 3} Output: 1 5 3 5 / \ 1 3 Input: arr[] = {3, 7, 4, 8} Output: 3 7 4 8 8 / 7 / \ 3 4 Approach: We have already seen an algorithm here that takes O(NlogN) time on an average but can get to O(N2) in the worst case.In this art
13 min read
Cartesian Tree Sorting
Cartesian Sort is an Adaptive Sorting as it sorts the data faster if data is partially sorted. In fact, there are very few sorting algorithms that make use of this fact. For example consider the array {5, 10, 40, 30, 28}. The input data is partially sorted too as only one swap between “40” and “28” results in a completely sorted order.  See how Car
15+ min read
Program to determine the quadrant of the cartesian plane
Given co-ordinates (x, y), determine the quadrant of the cartesian plane. Image_source : wikipedia.org Examples : Input : x = 1, y = 1 Output : lies in 1st quadrant Input : x = 0, y = 0 Output : lies at origin There are 9 conditions that needs to be checked to determine where does the points lies - If in first quadrant then, x &gt; 0 and y &gt; 0 I
6 min read
Cartesian Product of Two Sets
Let A and B be two sets, Cartesian productA × B is the set of all ordered pair of elements from A and B A × B = {{x, y} : x ? A, y ? B} Let A = {a, b, c} and B = {d, e, f} The Cartesian product of two sets is A x B = {a, d}, {a, e}, {a, f}, {b, d}, {b, e}, {b, f}, {c, d}, {c, e}, {c, f}}A has 3 elements and B also has 3 elements. The Cartesian Prod
5 min read
Program to convert polar co-ordinates to equivalent cartesian co-ordinates
Given two integers r and ? (in degree) representing polar coordinates of a point (r, ?), the task is to find the Cartesian coordinates of the given point. Examples: Input: r = 1.4142, ? = 45Output: 1.000, 1.000 Input: r = 3, ? = 30Output: 2.598, 1.500 Approach: Let the cartesian coordinates of the point be (x, y). The polar coordinates and the Cart
4 min read
Find number of Polygons lying inside each given Polygons on Cartesian Plane
Given N non-intersecting nested polygons, and a 2D array arr[][] of pairs, where each cell of the array represents the coordinates of the vertices of a polygon. The task is to find the count of polygons lying inside each polygon. Examples: Input: N = 3, arr[][][] = {{{-2, 2}, {-1, 1}, {2, 2}, {2, -1}, {1, -2}, {-2, -2}}, {{-1, -1}, {1, -1}, {1, 1}}
10 min read
Grouping robots on cartesian plane
In a 2D array robots[][], and an integer value K, where robots[i][j] represent the position of a robot on the cartesian plan. The task is to count the number of minimum groups that are formed by the robots such that the distance between robots in a group should be &lt;= K. Note: If two robots, 'a' and 'b', belong to the same group, and 'a' and 'd'
11 min read
Number of possible Triangles in a Cartesian coordinate system
Given n points in a Cartesian coordinate system. Count the number of triangles formed. Examples: Input : point[] = {(0, 0), (1, 1), (2, 0), (2, 2) Output : 3 Three triangles can be formed from above points. A simple solution is to check if the determinant of the three points selected is non-zero or not. The following determinant gives the area of a
7 min read
Complexity of different operations in Binary tree, Binary Search Tree and AVL tree
In this article, we will discuss the complexity of different operations in binary trees including BST and AVL trees. Before understanding this article, you should have a basic idea about Binary Tree, Binary Search Tree, and AVL Tree. The main operations in a binary tree are: search, insert and delete. We will see the worst-case time complexity of t
4 min read
Maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST
Given a binary tree, the task is to print the maximum sum of nodes of a sub-tree which is also a Binary Search Tree.Examples: Input : 7 / \ 12 2 / \ \ 11 13 5 / / \ 2 1 38 Output:44 BST rooted under node 5 has the maximum sum 5 / \ 1 38 Input: 5 / \ 9 2 / \ 6 3 / \ 8 7 Output: 8 Here each leaf node represents a binary search tree also a BST with su
12 min read
Article Tags :
Practice Tags :