How to calculate a Binary Tree’s height using array iteration in Ruby

We go through all the levels until the lowest one.If a sub tree has no left or right child then such child can be represented as 0, as long as the sub tree isn’t in the lowest level in the binary tree.Figure 2: Modified binary tree from Figure 1.tree = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] (T0)* array representation of Figure2Numerically, we can compute the positions of the left and right children of each node:left child of tree[i] is at index 2*i + 1 (T1)right child of tree[i] is at index 2*i + 2 (T2)As we can see from figure 2 we can tell how tall a tree is — that is we just need to count how many nodes there are from the root down to the lowest element (including the root and the lowest element) along the longest branch..But when it’s already in array form, how do we know how tall it is?First we must have a general formula for the height of any tree:height = 1 + max of(left_child_height, right_child_height) (T3)For multilevel trees then we can conclude that in order to compute the height of any sub-tree (and the tree itself) we first must compute the heights of the left and right children and then find the higher between the two..In computing the heights of these two children we need to compute the heights of their respective children and so on.Having this we can now begin to outline an algorithm for computing the height of multilevel binary trees..There are two methods we can take, one is using iterations or loops, and the other, because of the repetitive nature of the steps (previous paragraph), is using recursion..I will follow up this article with a discussion on how to use recursion to do this..However, that would be too easy..So let’s learn the hard way first: we’ll do this using iteration.Iterative MethodWe will use the tree array T0 above to illustrate this processStep 0: Declare a heights array which will store the heights of each sub tree.heights = [] (S0.1)Step 1: Iterate through the array — since we need to compute the heights of the descendants first, we iterate from the last element..And instead of using each method directly in the tree array we will use it for the indices of each element.(tree.length – 1).downto(0) do |i| (S1.1)Step 2: For each element, find initial height — if the element is zero (meaning it’s actually a nil node) then initial height is 0, else it is 1.initial_height = tree[i] == 0?.0 : 1 (S2.1)Step 3: Find height of left child — inside heights array, if the element has a left child then the height of this child is equal to:left_child_height = heights[left_child_index] (S3.1)In the above, the left_child_index can be computed as follows:left_child_index = heights.length – i – 1 (S3.2)I came up with S3.2 through a little trial and error..In the simulation that will follow these series of steps I will make mention of it.To summarize though, I initially intended to unshift each descendant’s heights into heights so that the heights of each element would have the same indices as the element itself has on trees..But as I’ll later note, using unshift for this will be taxing resource wise for large array inputs.So then I decided to use push..Each height will then be ordered in reverse compared to their corresponding elements’ order in tree.. More details

Leave a Reply