Learn basic concept of c , c++ and python programming in regularcodes.com

Spread the post

Finding height of a binary search tree without using recursion.

How to find Binary Search Tree height using iterative approach ? The two conventions of count height of BST.

1) By Node: (Number of Nodes having from Root node to longest (deepest) path leaf)

2) By Edge: (Number of Edge are connected having from Root node to longest(deepest) leaf).

View and Edit This Tree

Try it Yourself


Algorithm

Height of BST by node

Following data are inserted BST tree [ 452, 401, 550, 429, 452, 593, 413, 521, 576, 428 ]

View and Edit This Tree Try it Yourself

452401550452593429413576428521

Longest Path:

From root to leaf is [452, 401, 429, 413, 428].

Height: Height of this Tree By node is 5.

Height of BST by edge

Following data are inserted BST tree [ 582, 529, 600, 511, 565, 491, 511, 575, 442, 417, 443 ].

View and Edit This Tree Try it Yourself


582529511565491442443417575600

Longest Path:

From root to leaf is [582, 529, 511, 491, 442, 443].

Height: count BST height by edge in following formula. (Number of longest path from root to leaf -1). In this case (6-1)=5

C code implement to Get height of BST. Look at below to iterative approach.

Othere Example:

In this example showing both approaches Height by Nodes and by Edges.

View and Edit This Tree

Try it Yourself


50703020101560808447

Result:

Height of BST by Nodes : 5

Height of BST by Edges : 4

Code execution Process:

Code execution of above given tree.

See Execution Process


Stack Areamainqueue(pointer)root(pointer)count_heightheight (int) =5temp(pointer) Heap Areastruct Treedata (int)= 50left_child (pointer) right_child (pointer) struct Treedata (int)= 70left_child (pointer) right_child (pointer) struct Treedata (int)= 30left_child (pointer) right_child (pointer) struct Treedata (int)= 20left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 10left_child (pointer)= NULLright_child (pointer) struct Treedata (int)= 15left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 60left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 80left_child (pointer)= NULLright_child (pointer) struct Treedata (int)= 84left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 47left_child (pointer)= NULLright_child (pointer)= NULLstruct Queueheight (int)= 1node (pointer) next (pointer) struct Queueheight (int)= 2node (pointer) next (pointer) struct Queueheight (int)= 2node (pointer) next (pointer) struct Queueheight (int)= 3node (pointer) next (pointer) struct Queueheight (int)= 3node (pointer) next (pointer) struct Queueheight (int)= 3node (pointer) next (pointer) struct Queueheight (int)= 3node (pointer) next (pointer) struct Queueheight (int)= 4node (pointer) next (pointer) struct Queueheight (int)= 4node (pointer) next (pointer) struct Queueheight (int)= 5node (pointer) next (pointer)= NULL

Visualize all execution steps Visualize Code

C program to count height of BST using queue.

Output

Spread the post

Recommended Posts: