Find height of a binary tree represented by the parent array
Given an array representing the parent-child relationship in a binary tree, find the tree’s height without building it. The parent-child relationship is defined by (A[i], i) for every index i in array A. The root node’s value will be i if -1 is present at index i in the array.
The depth of a “node” is the total number of edges from the node to the tree’s root node. The root is the only node whose depth is 0.
The height of a “node” is the total number of edges on the longest path from the node to a leaf. The height of a “tree” would be the height of its root node, or equivalently, the depth of its deepest node. A leaf node will have a height of 0.
For example,
Index: [0, 1, 2, 3, 4, 5, 6, 7]
- -1 is present at index 0, which implies that the binary tree root is node 0.
- 0 is present at index 1 and 2, which implies that the left and right children of node 0 are 1 and 2.
- 1 is present at index 3, which implies that the left or the right child of node 1 is 3.
- 2 is present at index 4 and 5, which implies that the left and right children of node 2 are 4 and 5.
- 4 is present at index 6 and 7, which implies that the left and right children of node 4 are 6 and 7.
The corresponding binary tree is:
Related Post:
A simple solution would be to construct the binary tree using the parent array, as demonstrated in the above post. After the tree is constructed, calculate its height. The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the size of the parent array. However, as per problem constraints, the height should be calculated without building the tree.
The idea is to calculate the depth of every node using recursion and return the maximum depth found. Since the node’s depth is the total number of edges from the node to the root, we need to trace the node’s path to the root node using the parent-child relationship. We can do this by recursively traversing the parent array. The algorithm can be implemented as follows in C, Java, and Python:
C
|
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 |
#include <stdio.h> // Recursive function to calculate the depth of the i'th node in `parent[]` int findDepth(int parent[], int i) { // A root node will have a depth of 0 if (parent[i] == -1) { return 0; } // depth of the i'th node = 1 + depth of its parent return 1 + findDepth(parent, parent[i]); } // Function to calculate the height of a binary tree represented by // parent array int findHeight(int parent[], int n) { // keep track of the height of a tree int height = -1; // calculate the depth of each tree node `i` and keep track of // the maximum depth for (int i = 0; i < n; i++) { int depth = findDepth(parent, i); if (height < depth) { height = depth; } } return height; } int main(void) { int parent[] = {-1, 0, 0, 1, 2, 2, 4, 4}; int n = sizeof(parent)/sizeof(parent[0]); printf("The height of the binary tree is %d", findHeight(parent, n)); return 0; } |
Output:
The height of the binary tree is 3
Java
|
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 |
class Main { // Recursive function to calculate the depth of the i'th node in `parent[]` public static int findDepth(int[] parent, int i) { // A root node will have a depth of 0 if (parent[i] == -1) { return 0; } // depth of the i'th node = 1 + depth of its parent return 1 + findDepth(parent, parent[i]); } // Function to calculate the height of a binary tree represented by // parent array public static int findHeight(int[] parent) { // keep track of the height of a tree int height = -1; // calculate the depth of each tree node `i` and keep track of // the maximum depth for (int i = 0; i < parent.length; i++) { height = Integer.max(height, findDepth(parent, i)); } return height; } public static void main(String[] args) { int[] parent = {-1, 0, 0, 1, 2, 2, 4, 4}; System.out.println("The height of the binary tree is " + findHeight(parent)); } } |
Output:
The height of the binary tree is 3
Python
|
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 |
# Recursive function to calculate the depth of the i'th node in `parent[]` def findDepth(parent, i): # A root node will have a depth of 0 if parent[i] == -1: return 0 # depth of the i'th node = 1 + depth of its parent return 1 + findDepth(parent, parent[i]) # Function to calculate the height of a binary tree represented by # parent array def findHeight(parent): # keep track of the height of a tree height = -1 # calculate the depth of each tree node `i` and keep track of # the maximum depth for i in range(len(parent)): height = max(height, findDepth(parent, i)) return height if __name__ == '__main__': parent = [-1, 0, 0, 1, 2, 2, 4, 4] print('The height of the binary tree is', findHeight(parent)) |
Output:
The height of the binary tree is 3
The time complexity of the above solution is O(n2), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree.
Note that the findDepth() routine has an optimal substructure since it can be recursively broken down into smaller sub-routines, i.e., findDepth(i) = 1 + findDepth(parent[i]). It also exhibits overlapping subproblems since the same subproblem is solved over and over again.
We know that problems having optimal substructure and overlapping subproblems can be solved using dynamic programming. Following is the dynamic programming implementation in C, Java, and Python, where subproblem solutions are memoized rather than computed repeatedly. The solution uses an auxiliary array to store the depth of each node.
C
|
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 |
#include <stdio.h> // Recursive function to calculate the depth of the i'th node in `parent[]` int findDepth(int parent[], int depth[], int i) { // A root node will have a depth of 0 if (parent[i] == -1) { return 0; } // If the depth of the i'th node is already calculated, return it if (depth[i] != 0) { return depth[i]; } // depth of the i'th node = 1 + depth of its parent return 1 + findDepth(parent, depth, parent[i]); } // Function to calculate the height of a binary tree represented by // parent array int findHeight(int parent[], int n) { // keep track of the height of a tree int height = -1; // create an auxiliary array for storing the depth of each tree node int depth[n]; for (int i = 0; i < n; i++) { depth[i] = 0; } // calculate the depth of each tree node `i` and keep track of // the maximum depth for (int i = 0; i < n; i++) { depth[i] = findDepth(parent, depth, i); if (height < depth[i]) { height = depth[i]; } } return height; } int main(void) { int parent[] = {-1, 0, 0, 1, 2, 2, 4, 4}; int n = sizeof(parent)/sizeof(parent[0]); printf("The height of the binary tree is %d", findHeight(parent, n)); return 0; } |
Output:
The height of the binary tree is 3
Java
|
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 |
class Main { // Recursive function to calculate the depth of the i'th node in `parent[]` public static int findDepth(int[] parent, int[] depth, int i) { // A root node will have a depth of 0 if (parent[i] == -1) { return 0; } // If the depth of the i'th node is already calculated, return it if (depth[i] != 0) { return depth[i]; } // depth of the i'th node = 1 + depth of its parent return 1 + findDepth(parent, depth, parent[i]); } // Function to calculate the height of a binary tree represented by // parent array public static int findHeight(int[] parent) { // keep track of the height of a tree int height = -1; // create an auxiliary array for storing the depth of each tree node int[] depth = new int[parent.length]; // calculate the depth of each tree node `i` and keep track of // the maximum depth for (int i = 0; i < parent.length; i++) { depth[i] = findDepth(parent, depth, i); height = Integer.max(height, depth[i]); } return height; } public static void main(String[] args) { int[] parent = {-1, 0, 0, 1, 2, 2, 4, 4}; System.out.println("The height of the binary tree is " + findHeight(parent)); } } |
Output:
The height of the binary tree is 3
Python
|
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 |
# Recursive function to calculate the depth of the i'th node in `parent[]` def findDepth(parent, depth, i): # A root node will have a depth of 0 if parent[i] == -1: return 0 # If the depth of the i'th node is already calculated, return it if depth[i] != 0: return depth[i] # depth of the i'th node = 1 + depth of its parent return 1 + findDepth(parent, depth, parent[i]) # Function to calculate the height of a binary tree represented by # parent array def findHeight(parent): # keep track of the height of a tree height = -1 # create an auxiliary array for storing the depth of each tree node depth = [0] * len(parent) # calculate the depth of each tree node `i` and keep track of # the maximum depth for i in range(len(parent)): depth[i] = findDepth(parent, depth, i) height = max(height, depth[i]) return height if __name__ == '__main__': parent = [-1, 0, 0, 1, 2, 2, 4, 4] print('The height of the binary tree is', findHeight(parent)) |
Output:
The height of the binary tree is 3
The time complexity of the above solution is O(n) since the depth of every node is evaluated only once. The additional space used by the program is O(n).
Here’s a bottom-up iterative version of the above top-down recursive solution in C, Java, and Python:
C
|
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 |
#include <stdio.h> // Function to calculate the height of a binary tree represented by // parent array int findHeight(int parent[], int n) { // create an auxiliary array for storing the depth of each tree node int depth[n]; for (int i = 0; i < n; i++) { depth[i] = 0; } // keep track of the height of a tree int height = -1; // iteratively calculate the depth of each tree node `i` for (int i = 0; i < n; i++) { // initialize the depth of i'th node with 0 (the depth of a single node) int depth_i = 0; // trace the path from the i'th node back to the root for (int k = i; parent[k] != -1; k = parent[k]) { // if the depth of the k'th node is already calculated if (depth[k] != 0) { depth_i += depth[k]; break; } depth_i++; } // save subproblem solution depth[i] = depth_i; // keep track of the maximum depth if (height < depth[i]) { height = depth[i]; } } return height; } int main(void) { int parent[] = {-1, 0, 0, 1, 2, 2, 4, 4}; int n = sizeof(parent)/sizeof(parent[0]); printf("The height of the binary tree is %d", findHeight(parent, n)); return 0; } |
Output:
The height of the binary tree is 3
Java
|
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 |
class Main { // Function to calculate the height of a binary tree represented by // parent array public static int findHeight(int[] parent) { // create an auxiliary array for storing the depth of each tree node int[] depth = new int[parent.length]; // keep track of the height of a tree int height = -1; // iteratively calculate the depth of each tree node `i` for (int i = 0; i < parent.length; i++) { // initialize the depth of i'th node with 0 (the depth of a single node) int depth_i = 0; // trace the path from the i'th node back to the root for (int k = i; parent[k] != -1; k = parent[k]) { // if the depth of the k'th node is already calculated if (depth[k] != 0) { depth_i += depth[k]; break; } depth_i++; } // save subproblem solution depth[i] = depth_i; // keep track of the maximum depth height = Integer.max(height, depth[i]); } return height; } public static void main(String[] args) { int[] parent = {-1, 0, 0, 1, 2, 2, 4, 4}; System.out.println("The height of the binary tree is " + findHeight(parent)); } } |
Output:
The height of the binary tree is 3
Python
|
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 |
# Function to calculate the height of a binary tree represented by # parent array def findHeight(parent): # create an auxiliary array for storing the depth of each tree node depth = [0] * len(parent) # keep track of the height of a tree height = -1 # iteratively calculate the depth of each tree node `i` for i in range(len(parent)): # initialize the depth of i'th node with 0 (the depth of a single node) depth_i = 0 # trace the path from the i'th node back to the root k = i while parent[k] != -1: # if the depth of the k'th node is already calculated if depth[k] != 0: depth_i += depth[k] break depth_i += 1 k = parent[k] # save subproblem solution depth[i] = depth_i # keep track of the maximum depth height = max(height, depth[i]) return height if __name__ == '__main__': parent = [-1, 0, 0, 1, 2, 2, 4, 4] print('The height of the binary tree is', findHeight(parent)) |
Output:
The height of the binary tree is 3
The time complexity of the above solution is O(n), and the auxiliary space used by the program is O(n).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)