Calculate depth of a full Binary tree from Preorder | GeeksforGeeks


Hello friends!
And, welcome to another tutorial on GeeksforGeeks. In this video we are going to understand the
program which calculates depth of a full binary tree from preorder..First, let us take
an example.. We start from depth 0..The preorder is given
as a string with two possible characters.‘l’ denotes the leaf ‘n’
denotes internal node The given tree can be seen as a full binary
tree where every node has 0 or two children. The two children of a node can ‘n’
or ‘l’ or mix of both. .. Now, let us see the algorithm which will
assist us in this Let us also have a sample tree to test our
algorithm.. We pass the tree array, and n to function
findDepth…n are the number of nodes in the binary
tree. We take another variable index which we initialize
to 0 We pass the tree array, n and index to findDepthRec
Function.. As index is not greater than n or the element
at index is not l, we increment index.. So, index
will be equal to 1 We calculate height of left subtree… So,
we call the findDepthRec function with index as 1..
Using a call stack.. As index is not>=n.. We check if the
element in the tree array at index 1 is l.. As it is true, we
return 0 Now we calculate height of right subtree.
So, we increment index.. Next, we pass tree, n and index As index is not>=n and the element at
index 2 in tree array is not l.. We increment index. Next, we call for the findDepthRec function
with index=3 As index is not greater than n but element
at index 3 in array tree is l, we return 0 We increment index Next, we calculate hieght of right subtree..
So, we pass index as 4. As element at index 4 is l, we return 0 We return max of left and right +1, so, we
return 1 Again, we return max of left,right +1.. As
right is greater>left, so we return 1+1=2 So this is the depth of this binary tree.
With this we come to an end of this tutorial. For any doubts or suggestions please leave
them in the comment section below. Thanks for watching!

Leave a Reply

Your email address will not be published. Required fields are marked *