Given an array of values. The task is to implement a Binary Search Tree using values of the array where every node stores the maximum number of nodes in the path starting from the node itself and ending at any leaf of the tree.
Note: The maximum number of nodes in the path from any node to any leaf node in a BST is the height of the subtree rooted at that node.
Examples:
Input : arr[] = {1, 2, 3, 4, 5, 6, 7}
Output :
data = 1 height = 6
data = 2 height = 5
data = 3 height = 4
data = 4 height = 3
data = 5 height = 2
data = 6 height = 1
data = 7 height = 0Input : arr[] = {4, 12, 10, 5, 11, 8, 7, 6, 9}
Output :
data = 4 height = 6
data = 5 height = 3
data = 6 height = 0
data = 7 height = 1
data = 8 height = 2
data = 9 height = 0
data = 10 height = 4
data = 11 height = 0
data = 12 height = 5
The idea is to add nodes in the BST fashion. Height of the parent say P will be updated only when the new node is added to the subtree which contributes to the height of P AND (logical) the height of the subtree has increased as well after the addition of the new node.
Let’s say that an existing tree is (data of node is in red and current height of node in green):
Now we are going to add a new node of containing the value 6, the route taken by node in order to get added has been highlighted in blue:
With addition of the new node, the height of it’s immediate parent will be increased (only if the height of the immediate parent of node containing 6 is being affected by this addition – which in this case is true). Once the height of parent is incremented, it will check whether the sub-tree where parent is present is the main contributory to the height of node having that sub-tree as a child, if yes then height of that node will be increased – in short the height incrementation if propagated upwards.
Now we are going to add another node containing value 9 & the path it will take to get added to its final position is in blue:
Since the height of the immediate parent of the node containing value 9 is not getting affected by this addition, its parent’s height won’t get affected and height incrementation won’t get propagated upwards.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include<bits/stdc++.h>using namespace std;// Structure containing basic template od a nodestruct node { // Stores the data and current height of the node int data; int height; struct node* right; struct node* left;};int indicator = 0;void left_insert(struct node*, struct node*);void right_insert(struct node*, struct node*);// Inorder traversal of the treevoid traverse(struct node* head){ if (head != NULL) { traverse(head->left); cout << " data = " << head->data; cout<< " height = " << head->height << endl; traverse(head->right); }}// Insertion to the left sub-treevoid left_insert(struct node* head, struct node* temp){ // Child node of Current head struct node* child = NULL; if (head->data > temp->data) { if (head->left == NULL) { indicator = 1; child = head->left = temp; } else { left_insert(head->left, temp); child = head->left; } } else { right_insert(head, temp); } if ((indicator == 1) && (child != NULL)) { if (head->height > child->height) { // Ending propagation to height of above nodes indicator = 0; } else { head->height += 1; } }}// Insertion to the right sub-treevoid right_insert(struct node* head, struct node* temp){ // Child node of Current head struct node* child = NULL; if (head->data < temp->data) { if (head->right == NULL) { indicator = 1; child = head->right = temp; } else { right_insert(head->right, temp); child = head->right; } } else { left_insert(head, temp); } if ((indicator == 1) && (child != NULL)) { if (head->height > child->height) { // Ending propagation to height of above nodes indicator = 0; } else { head->height += 1; } }}// Function to create node and push// it to its appropriate positionvoid add_nodes(struct node** head, int value){ struct node *temp_head = *head, *temp; if (*head == NULL) { // When first node is added *head = new node(); (*head)->data = value; (*head)->height = 0; (*head)->right = (*head)->left = NULL; } else { temp = new node(); temp->data = value; temp->height = 0; temp->right = temp->left = NULL; left_insert(temp_head, temp); temp_head = *head; indicator = 0; }}// Driver Codeint main(){ struct node *head = NULL, *temp_head = NULL; add_nodes(&head, 4); add_nodes(&head, 12); add_nodes(&head, 10); add_nodes(&head, 5); add_nodes(&head, 11); add_nodes(&head, 8); add_nodes(&head, 7); add_nodes(&head, 6); add_nodes(&head, 9); temp_head = head; // Traversing the tree to display // the updated height values traverse(temp_head); return 0;}// This code is contributed by rrrtnx. |
C
// C implementation of above approach#include <stdio.h>#include <stdlib.h>// Structure containing basic template od a nodestruct node { // Stores the data and current height of the node int data; int height; struct node* right; struct node* left;};int indicator = 0;void left_insert(struct node*, struct node*);void right_insert(struct node*, struct node*);// Inorder traversal of the treevoid traverse(struct node* head){ if (head != NULL) { traverse(head->left); printf(" data = %d", head->data); printf(" height = %d\n", head->height); traverse(head->right); }}// Insertion to the left sub-treevoid left_insert(struct node* head, struct node* temp){ // Child node of Current head struct node* child = NULL; if (head->data > temp->data) { if (head->left == NULL) { indicator = 1; child = head->left = temp; } else { left_insert(head->left, temp); child = head->left; } } else { right_insert(head, temp); } if ((indicator == 1) && (child != NULL)) { if (head->height > child->height) { // Ending propagation to height of above nodes indicator = 0; } else { head->height += 1; } }}// Insertion to the right sub-treevoid right_insert(struct node* head, struct node* temp){ // Child node of Current head struct node* child = NULL; if (head->data < temp->data) { if (head->right == NULL) { indicator = 1; child = head->right = temp; } else { right_insert(head->right, temp); child = head->right; } } else { left_insert(head, temp); } if ((indicator == 1) && (child != NULL)) { if (head->height > child->height) { // Ending propagation to height of above nodes indicator = 0; } else { head->height += 1; } }}// Function to create node and push// it to its appropriate positionvoid add_nodes(struct node** head, int value){ struct node *temp_head = *head, *temp; if (*head == NULL) { // When first node is added *head = malloc(sizeof(**head)); (*head)->data = value; (*head)->height = 0; (*head)->right = (*head)->left = NULL; } else { temp = malloc(sizeof(*temp)); temp->data = value; temp->height = 0; temp->right = temp->left = NULL; left_insert(temp_head, temp); temp_head = *head; indicator = 0; }}// Driver Codeint main(){ struct node *head = NULL, *temp_head = NULL; add_nodes(&head, 4); add_nodes(&head, 12); add_nodes(&head, 10); add_nodes(&head, 5); add_nodes(&head, 11); add_nodes(&head, 8); add_nodes(&head, 7); add_nodes(&head, 6); add_nodes(&head, 9); temp_head = head; // Traversing the tree to display // the updated height values traverse(temp_head); return 0;} |
Java
// Java implementation of above approachclass GFG{// Structure containing basic template od a nodestatic class node { // Stores the data and current height of the node int data; int height; node right; node left;}static int indicator = 0;// Inorder traversal of the treestatic void traverse(node head){ if (head != null) { traverse(head.left); System.out.printf(" data = %d", head.data); System.out.printf(" height = %d\n", head.height); traverse(head.right); }}// Insertion to the left sub-treestatic void left_insert(node head, node temp){ // Child node of Current head node child = null; if (head.data > temp.data) { if (head.left == null) { indicator = 1; child = head.left = temp; } else { left_insert(head.left, temp); child = head.left; } } else { right_insert(head, temp); } if ((indicator == 1) && (child != null)) { if (head.height > child.height) { // Ending propagation to height of above nodes indicator = 0; } else { head.height += 1; } }}// Insertion to the right sub-treestatic void right_insert(node head, node temp){ // Child node of Current head node child = null; if (head.data < temp.data) { if (head.right == null) { indicator = 1; child = head.right = temp; } else { right_insert(head.right, temp); child = head.right; } } else { left_insert(head, temp); } if ((indicator == 1) && (child != null)) { if (head.height > child.height) { // Ending propagation to height of above nodes indicator = 0; } else { head.height += 1; } }}// Function to create node and push// it to its appropriate positionstatic node add_nodes(node head, int value){ node temp_head = head, temp; if (head == null) { // When first node is added head = new node(); (head).data = value; (head).height = 0; (head).right = (head).left = null; } else { temp = new node(); temp.data = value; temp.height = 0; temp.right = temp.left = null; left_insert(temp_head, temp); temp_head = head; indicator = 0; } return head;}// Driver Codepublic static void main(String args[]){ node head = null, temp_head = null; head = add_nodes(head, 4); head = add_nodes(head, 12); head = add_nodes(head, 10); head = add_nodes(head, 5); head = add_nodes(head, 11); head = add_nodes(head, 8); head = add_nodes(head, 7); head = add_nodes(head, 6); head = add_nodes(head, 9); temp_head = head; // Traversing the tree to display // the updated height values traverse(temp_head);}}// This code is contributed by Arnab Kundu |
Python3
# Python implementation of above approach# Structure containing basic template od a nodeclass node: def __init__(self) -> None: # Stores the data and current height of the node self.data = 0 self.height = 0 self.right = None self.left = None# Inorder traversal of the treedef traverse(head: node) -> None: if (head != None): traverse(head.left) print(" data = {}".format(head.data), end="") print(" height = {}".format(head.height)) traverse(head.right)# Insertion to the left sub-treedef left_insert(head: node, temp: node) -> None: global indicator # Child node of Current head child = None if (head.data > temp.data): if (head.left == None): indicator = 1 child = head.left = temp else: left_insert(head.left, temp) child = head.left else: right_insert(head, temp) if ((indicator == 1) and (child != None)): if (head.height > child.height): # Ending propagation to height of above nodes indicator = 0 else: head.height += 1# Insertion to the right sub-treedef right_insert(head: node, temp: node) -> None: global indicator # Child node of Current head child = None if (head.data < temp.data): if (head.right == None): indicator = 1 child = head.right = temp else: right_insert(head.right, temp) child = head.right else: left_insert(head, temp) if ((indicator == 1) and (child != None)): if (head.height > child.height): # Ending propagation to height of above nodes indicator = 0 else: head.height += 1# Function to create node and push# it to its appropriate positiondef add_nodes(head: node, value: int) -> node: global indicator temp_head = head temp = None if (head == None): # When first node is added head = node() (head).data = value (head).height = 0 (head).right = (head).left = None else: temp = node() temp.data = value temp.height = 0 temp.right = temp.left = None left_insert(temp_head, temp) temp_head = head indicator = 0 return head# Driver Codeif __name__ == "__main__": indicator = 0 head = None temp_head = None head = add_nodes(head, 4) head = add_nodes(head, 12) head = add_nodes(head, 10) head = add_nodes(head, 5) head = add_nodes(head, 11) head = add_nodes(head, 8) head = add_nodes(head, 7) head = add_nodes(head, 6) head = add_nodes(head, 9) temp_head = head # Traversing the tree to display # the updated height values traverse(temp_head)# This code is contributed by sanjeev2552 |
C#
// C# implementation of above approachusing System;public class GFG { // Structure containing basic template od a node public class node { // Stores the data and current height of the node public int data; public int height; public node right; public node left; } static int indicator = 0; // Inorder traversal of the tree static void traverse(node head) { if (head != null) { traverse(head.left); Console.Write(" data = {0}", head.data); Console.Write(" height = {0}\n", head.height); traverse(head.right); } } // Insertion to the left sub-tree static void left_insert(node head, node temp) { // Child node of Current head node child = null; if (head.data > temp.data) { if (head.left == null) { indicator = 1; child = head.left = temp; } else { left_insert(head.left, temp); child = head.left; } } else { right_insert(head, temp); } if ((indicator == 1) && (child != null)) { if (head.height > child.height) { // Ending propagation to height of above nodes indicator = 0; } else { head.height += 1; } } } // Insertion to the right sub-tree static void right_insert(node head, node temp) { // Child node of Current head node child = null; if (head.data < temp.data) { if (head.right == null) { indicator = 1; child = head.right = temp; } else { right_insert(head.right, temp); child = head.right; } } else { left_insert(head, temp); } if ((indicator == 1) && (child != null)) { if (head.height > child.height) { // Ending propagation to height of above nodes indicator = 0; } else { head.height += 1; } } } // Function to create node and push // it to its appropriate position static node add_nodes(node head, int value) { node temp_head = head, temp; if (head == null) { // When first node is added head = new node(); (head).data = value; (head).height = 0; (head).right = (head).left = null; } else { temp = new node(); temp.data = value; temp.height = 0; temp.right = temp.left = null; left_insert(temp_head, temp); temp_head = head; indicator = 0; } return head; } // Driver Code public static void Main(String []args) { node head = null, temp_head = null; head = add_nodes(head, 4); head = add_nodes(head, 12); head = add_nodes(head, 10); head = add_nodes(head, 5); head = add_nodes(head, 11); head = add_nodes(head, 8); head = add_nodes(head, 7); head = add_nodes(head, 6); head = add_nodes(head, 9); temp_head = head; // Traversing the tree to display // the updated height values traverse(temp_head); }}// This code contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of above approach// Structure containing basic template od a nodeclass node{ constructor() { this.left; this.right; this.data; this.height; }}let indicator = 0;// Inorder traversal of the treefunction traverse(head){ if (head != null) { traverse(head.left); document.write(" data = " + head.data); document.write(" height = "+ head.height + "</br>"); traverse(head.right); }}// Insertion to the left sub-treefunction left_insert(head, temp){ // Child node of Current head let child = null; if (head.data > temp.data) { if (head.left == null) { indicator = 1; child = head.left = temp; } else { left_insert(head.left, temp); child = head.left; } } else { right_insert(head, temp); } if ((indicator == 1) && (child != null)) { if (head.height > child.height) { // Ending propagation to height // of above nodes indicator = 0; } else { head.height += 1; } }}// Insertion to the right sub-treefunction right_insert(head, temp){ // Child node of Current head let child = null; if (head.data < temp.data) { if (head.right == null) { indicator = 1; child = head.right = temp; } else { right_insert(head.right, temp); child = head.right; } } else { left_insert(head, temp); } if ((indicator == 1) && (child != null)) { if (head.height > child.height) { // Ending propagation to height // of above nodes indicator = 0; } else { head.height += 1; } }}// Function to create node and push// it to its appropriate positionfunction add_nodes(head, value){ let temp_head = head, temp; if (head == null) { // When first node is added head = new node(); (head).data = value; (head).height = 0; (head).right = (head).left = null; } else { temp = new node(); temp.data = value; temp.height = 0; temp.right = temp.left = null; left_insert(temp_head, temp); temp_head = head; indicator = 0; } return head;}// Driver codelet head = null, temp_head = null;head = add_nodes(head, 4);head = add_nodes(head, 12);head = add_nodes(head, 10);head = add_nodes(head, 5);head = add_nodes(head, 11);head = add_nodes(head, 8);head = add_nodes(head, 7);head = add_nodes(head, 6);head = add_nodes(head, 9);temp_head = head;// Traversing the tree to display// the updated height valuestraverse(temp_head);// This code is contributed by divyeshrabadiya07</script> |
Output:
data = 4 height = 6 data = 5 height = 3 data = 6 height = 0 data = 7 height = 1 data = 8 height = 2 data = 9 height = 0 data = 10 height = 4 data = 11 height = 0 data = 12 height = 5
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
