189-binary-search-tree-height-in-c

Reading Time: 3 minutes

First functionality of methods in binary search tree class is to count nodes of binary search tree recursively and to measure binary search tree height. Taking the data from previous example, and starting with following array { 53, 72, 14, 7, 17, 12, 1}; we obtain following binary tree.

binary-search-tree-height

As we can see, given binary search tree has 7 nodes with left hight of 4 and right height of 2. Bigger number is taken as overall height and that is in this example 4. We can count nodes of binary search tree with the following method

public int count_elements(node_in_sbt root)
{

int count = 1;
if (root != null)
{

if (root.left != null) count += count_elements(root.left);
if (root.right != null) count += count_elements(root.right);

}
return count;

}

Call of count_elements goes recursively:

int how_many = bst.count_elements(bst.root_of_the_tree);

We can find binary search tree height with following method:
public int tree_height_or_depth(node_in_sbt root)
{

int height = 1;
int left = 1;
int right = 1;
if (root != null)
{

if (root.left != null) left += tree_height_or_depth(root.left);
if (root.right != null) right += tree_height_or_depth(root.right);

}
height = Math.Max(left, right);
return height;

}

Call of tree_height_or_depth goes recursively:

int height_or_depth = bst.tree_height_or_depth(bst.root_of_the_tree);

Whole code for binary search class is given:

public class node_in_sbt
{

public int data_value;
public node_in_sbt left, right;
public node_in_sbt(int a)
{

this.data_value = a;
left = null;
right = null;

}

}
public class Tree
{

public node_in_sbt root_of_the_tree;
public Tree()
{

root_of_the_tree = null;

}
public Tree(int[] input)
{

root_of_the_tree = null;
for (int i = 0; i < input.Length; i++)
{

this.insert(this.root_of_the_tree, this.addNode(input[i]));

}

}
public node_in_sbt addNode(int int_data)
{

node_in_sbt temp = new node_in_sbt(int_data);
if (root_of_the_tree == null) root_of_the_tree = temp;
return temp;

}

public void insert(node_in_sbt root, node_in_sbt newNode)
{

while (root != null)

{

if (newNode.data_value > root.data_value)

{

if (root.right == null)
{

root.right = newNode;
MessageBox.Show(root.right.data_value.ToString(), “Right”);
break;

}
root = root.right;
MessageBox.Show(root.data_value.ToString(), “new root Right”);

}
else
{

if (root.left == null)
{

root.left = newNode;
MessageBox.Show(newNode.data_value.ToString(), “Left”);
break;

}
root = root.left;
MessageBox.Show(root.data_value.ToString(), “new root Left”);
}

}

}

public void ordered(node_in_sbt root)
{

string str_return = “”;
if (root != null)

{

ordered(root.left);
str_return += root.data_value.ToString() + ” “;
MessageBox.Show(str_return);
ordered(root.right);

}

}

public int count_elements(node_in_sbt root)
{

int count = 1;
if (root != null)
{

if (root.left != null) count += count_elements(root.left);
if (root.right != null) count += count_elements(root.right);

}
return count;

}
public int tree_height_or_depth(node_in_sbt root)
{

int height = 1;
int left = 1;
int right = 1;
if (root != null)
{

if (root.left != null) left += tree_height_or_depth(root.left);
if (root.right != null) right += tree_height_or_depth(root.right);

}
height = Math.Max(left, right);
return height;

}

}

private void cmd_Click(object sender, EventArgs e)
{

int[] input = { 53, 72, 14, 7, 17, 12, 1};
Tree bst = new Tree(input);
bst.ordered(bst.root_of_the_tree);
int how_many = bst.count_elements(bst.root_of_the_tree);
int height_or_depth = bst.tree_height_or_depth(bst.root_of_the_tree);

}

External links:

Binary Search Tree height on stackoverflow.com
Binary Search Tree height on www.cs.cmu.edu
Binary Search Tree height on www.geeksforgeeks.org
Binary Search Tree height on www.personal.kent.edu
Binary Search Tree height on algs4.cs.princeton.edu

Leave a Reply

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

*