Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

tree
data structures

What is the difference between the height and depth of a tree?

Behzad Ahmad

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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.

Height

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.

Depth

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.

RELATED TAGS

tree
data structures

CONTRIBUTOR

Behzad Ahmad
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring