Find height of a binary tree represented by the parent array

Given an array representing the parent-child relationship in a binary tree, discover the tree’s peak with out constructing it. The parent-child relationship is outlined by (A[i], i) for each index i in array A. The basis node’s worth can be i if -1 is current at index i within the array.

The depth of a “node” is the overall variety of edges from the node to the tree’s root node. The basis is the one node whose depth is 0.

The peak of a “node” is the overall variety of edges on the longest path from the node to a leaf. The peak of a “tree” could be the peak of its root node, or equivalently, the depth of its deepest node. A leaf node can have a peak of 0.

 
For instance,

Dad or mum: [-1, 0, 0, 1, 2, 2, 4, 4]
Index:  [0, 1, 2, 3, 4, 5, 6, 7]
 

  • -1 is current at index 0, which means that the binary tree root is node 0.
  • 0 is current at index 1 and a couple of, which means that the left and proper youngsters of node 0 are 1 and a couple of.
  • 1 is current at index 3, which means that the left or the best youngster of node 1 is 3.
  • 2 is current at index 4 and 5, which means that the left and proper youngsters of node 2 are 4 and 5.
  • 4 is current at index 6 and seven, which means that the left and proper youngsters of node 4 are 6 and seven.

The corresponding binary tree is:

Build Binary Tree from Parent Array

Practice this problem

 
Associated Put up:

Build a binary tree from a parent array

 
A easy answer could be to assemble the binary tree utilizing the mum or dad array, as demonstrated within the above publish. After the tree is constructed, calculate its peak. The time complexity of the above answer is O(n) and requires O(n) additional area, the place n is the scale of the mum or dad array. Nevertheless, as per drawback constraints, the peak ought to be calculated with out constructing the tree.

 
The thought is to calculate the depth of each node utilizing recursion and return the utmost depth discovered. For the reason that node’s depth is the overall variety of edges from the node to the foundation, we have to hint the node’s path to the foundation node utilizing the parent-child relationship. We will do that by recursively traversing the mum or dad array. The algorithm will be applied as follows in C, Java, and Python:

C

Download  Run Code

Output:

The peak of the binary tree is 3

Java

Download  Run Code

Output:

The peak of the binary tree is 3

Python

Download  Run Code

Output:

The peak of the binary tree is 3

The time complexity of the above answer is O(n2), the place n is the overall variety of nodes within the binary tree. The auxiliary area required by this system is O(h) for the decision stack, the place h is the peak of the tree.

 
Notice that the findDepth() routine has an optimal substructure since it may be recursively damaged down into smaller sub-routines, i.e., findDepth(i) = 1 + findDepth(mum or dad[i]). It additionally displays overlapping subproblems because the identical subproblem is solved time and again.

We all know that issues having optimum substructure and overlapping subproblems will be solved utilizing dynamic programming. Following is the dynamic programming implementation in C, Java, and Python, the place subproblem options are memoized slightly than computed repeatedly. The answer makes use of an auxiliary array to retailer the depth of every node.

C

Download  Run Code

Output:

The peak of the binary tree is 3

Java

Download  Run Code

Output:

The peak of the binary tree is 3

Python

Download  Run Code

Output:

The peak of the binary tree is 3

The time complexity of the above answer is O(n) because the depth of each node is evaluated solely as soon as. The extra area utilized by this system is O(n).

 
Right here’s a bottom-up iterative model of the above top-down recursive answer in C, Java, and Python:

C

Download  Run Code

Output:

The peak of the binary tree is 3

Java

Download  Run Code

Output:

The peak of the binary tree is 3

Python

Download  Run Code

Output:

The peak of the binary tree is 3

The time complexity of the above answer is O(n), and the auxiliary area utilized by this system is O(n).

Thanks for studying.

Please use our online compiler to publish code in feedback utilizing C, C++, Java, Python, JavaScript, C#, PHP, and plenty of extra standard programming languages.

Like us? Refer us to your mates and assist us develop. Completely happy coding 🙂

More Posts