The height and depth of a tree are similar terms, but not identical. Before understanding and comparing them, let’s look at some key terms regarding trees.
Node: A node is a structure or location where we can store our data.
Edge: An edge is a connection or path between two nodes.
- The highest node of the tree is called the root node.
- A node that has no child is called a leaf node.
- Any two nodes which are connected by an edge are called adjacent nodes.
Let’s look at the following tree.
The height of a node is the number of edges on the longest path from that node to a leaf node.
As such, the height of the tree would be the height of its root node. Meanwhile, the leaf nodes have a height of 0.
Let’s look at the following tree, which gives the height of each node.
The depth of a node is the number of edges from that node to the tree’s root node. As such, the depth of the whole tree would be the depth of its deepest leaf node. The root node has a depth of 0.
Let’s look at the following tree, which gives the depth of each node.
As you can see, the tree’s height and depth are the same, but the way they are calculated is different.
Free Resources