Same is true if node has only right subtree. What if a node has a left subtree? Then height of subtree at that node will be height of left subtree + 1 (for the node itself). What will be height of empty tree where root itself is null? It will be zero. What if we go bottom up instead of measuring distance of leaf nodes from root? What will be height of leaf node? At leaf node, there is no tree below it, hence height should be 1, which is node itself.
As we will traversing each node of tree complexity will be O(n) and we need O(2logn) space to store distance for each leaf node. Note that we have multiple lea nodes, however we chose the node which s farthest from the root node.īrute force method to find height will be to calculate distance of each node from the root and take the maximum of it. For example, height of tree given below is 5, distance between node(10) and node(8). First of all, what do we mean by height of binary search tree or height of binary tree? Height of tree is the maximum distance between the root node and any leaf node of the tree. One of the most basic problems on binary search tree is to find height of binary search tree or binary tree.
0 kommentar(er)
