BINARY SEARCH TREES: HEIGHT
I’m continuing my learning of the Binary Search Trees, so this post contains notes that I took on Height in the Binary Search Tree.
Height of a Tree: Is the longest path from our root node to it’s farthest node, the leaf node.
It’s like counting all the edges from the root node to the leaf node, and whichever has the longest path, that’s the height of the tree.
Height of a Tree with 1 Node: 0
A Tree with 1 Node has a height of 0, since there are no edges, which it basically means the Tree only has a root node.
Height of an Empty Tree: -1.
An Empty Tree has a height of -1, because it is empty.
BINARY SEARCH TREES: HEIGHT
Find the longest path from the Root Node to the Leaf Nodes
The Root Node in this Tree is: 50
The Leaf Nodes in this Tree are: 15, 35, 63, 70, 85
_______50_______
/ \
__25__ __75_
/ \ / \
15 35 65 85
/ \ / \ / \ / \
null null null null null null null null
\
63
Counting the edges from 50 to 15 are: 2
Counting the edges from 50 to 35 are: 2
Counting the edges from 50 to 63 are: 4
Counting the edges from 50 to 70 are: 3
Counting the edges from 50 to 85 are: 2
The longest path for this tree is 4 nodes.
The Height of this tree is 4.
BINARY SEARCH TREE: HEIGHT
There will be two Height methods
1. in the BTS class, which will make the initial call.
2. in the node class.
class BST {
findHeight(){
// has no parameters
if(this.root)
// if the tree is empty, then skip down to “return -1”.
// if the tree is not empty, then execute the following code:
return this.root.findHeight(this.root);
// if the tree is not empty, then invoke the findHeight() method in the Node class, and pass in the root node as a starting point.
return -1;
// if the tree is empty, then skip down to “return -1”.
}
}
class Node {
findHeight(currentNode) {
// the findHeight() method is going to have “currentNode” as a parameter.
// the findHeight() method is going to be recursive and needs a base case
if(currentNode == Null)
// the findHeight() method is recursive, this is it’s base case
// if the currentNode is equal to null, then return -1
return -1;
// if the currentNode is equal to null, then return -1
let leftHeight = this.findHeight(currentNode.left)
// this is to go down the left subtree
let rightHeight = this.findHeight(currentNode.right)
// this is to go down the right subtree
return Math.max(leftHeight, rightHeight) +1;
// we need to find the max between the left and right subtree plus 1.
// we need to find the max, because we need to find the largest value between the left and right subtrees.
// the plus 1 is to account for the initial edge between the root node and the subtrees.
// so we take the largest between theft and right subtree and we add 1 to it, which will give us the height of a tree.
}
}
A
_______50_______
/ \
B C
__25__ __75_
/ \ / \
D E null null
15 35
/ \ / \
null null null null
In conclusion, the height of a Tree is the longest path from our root node to it’s farthest node, the leaf node, like counting all the edges from the root node to the leaf node, and whichever has the longest path, that’s the height of the tree.
