The diameter of a binary tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the binary tree.
The diameter can occur through:
- The binary tree's root, meaning that its longest path is from the left subtree through the root and down into the right subtree.
- The left or right subtree without passing through the binary tree's root.
let d stand for the binary tree's diameter
d = max(left_height + right_height + 1, max(left_diameter, right_diameter))
where:
left_height + right_height + 1is the diameter through the binary tree's root.max(left_diameter, right_diameter)is the max of each side's diameter, i.e. when the longest path does not pass through the binary tree's root.
Let's look at some examples to visualize the longest path of different binary trees. In these examples:
Nrepresents a node- A natural number represents a node that is in the longest path
- We count from the left to the right to find each node in the longest path
- The natural number of the last node in that path is the diameter
In other words, we are visually counting the longest path using natural numbers.
This binary tree's diameter is 5.
N
. .
N N
. .
N N
The longest path through this binary tree is all of the nodes:
3
. .
2 4
. .
1 5
This binary tree's diameter is 4.
N
. .
N N
. .
N N
Starting on the left, the longest path through this binary tree is shown by the numbers:
3
. .
2 4
. .
1 N
This binary tree's diameter is 9.
N
. .
N N
. .
N N
. .
N N
.
N
. .
N N
.
N
Starting on the left, the longest path through this binary tree is shown by the numbers:
7
. .
6 8
. .
5 9
. .
N 4
.
3
. .
N 2
.
1
This binary tree's diameter is 10. But this binary tree's diameter doesn't go through the tree's root node. Rather, it's longest path is only through the left subtree, starting at the binary tree's first left child (i.e. level 2).
N
. .
N N
. . .
N N N
. . .
N N N
. .
N N
. . . .
N N N N
.
N
Starting on the left, the longest path through this binary tree is shown by the numbers:
N
. .
5 N
. . .
4 6 N
. . .
N 3 7
. .
2 8
. . . .
N 1 N 9
.
10
Let's conceptualize an algorithm to find the diameter of a given binary search tree.
Let's start with a basic Node and Tree class structures.
class Node:
def __init__(self, value = None):
self.value = value
self.left = None
self.right = None
def get_value(self):
return self.value
def set_value(self, value):
self.value = value
def has_left_child(self):
return self.left is not None
def get_left_child(self):
return self.left
def set_left_child(self, node):
self.left = node
def has_right_child(self):
return self.right is not None
def get_right_child(self):
return self.right
def set_right_child(self, node):
self.right = node
class Tree:
def __init__(self):
self.root = None
def set_root(self, value):
self.root = Node(value)
def get_root(self):
return self.root
def insert(self, value):
pass
def delete(self, value):
pass
def search(self, value):
pass
def height(self):
pass
def diameter(self):
pass
The first step is to design the method that computes the height of tree, subtree, or node. The height is equal to number of nodes from the root to leaf on the longest path from the root.
For example, the longest path in this tree is from the root to the furthest leaf. Its height is 3.
3
. .
2 N
. .
1 N
Here's another example. There are 7 nodes on the longest path from the root to the furthest leaf. Its height is 7.
7
. .
6 N
. . .
N 5 N
. . .
N N 4
. .
N 3
. . . .
N N N 2
.
1
Another way to look at height is to traverse the tree and find all of the paths from root to leaf. The one with the most nodes is the height of the tree.
Using recursion, we can design the height like this:
def height(self):
if self.root is None:
return 0
return self._height(self.root, 0)
def _height(self, node, height=0):
if node is None:
return height
# Increment for this current node.
height += 1
# If this node is a leaf, return the current height.
if not node.has_left_child() and not node.has_right_child():
return height
# To save some steps, we'll only get the child height if there is a child.
left_height = 0
right_height = 0
if node.has_left_child():
left_height = self._height(node.get_left_child(), height)
if node.has_right_child():
right_height = self._height(node.get_right_child(), height)
return max(left_height, right_height)Recall how we compute the diameter:
d = max(left_height + right_height + 1, max(left_diameter, right_diameter))
What do you notice?
- Get the left child's height.
- Get the right child's height.
- Get the left child's diameter. <- we can do this recursively
- Get the right child's diameter. <- we can do this recursively
- Then plug the values into the above formula.
def diameter(self):
if self.root is None:
return 0
return self._diameter(self.root, 0)
def _diameter(self, node, diameter=0):
if node is None:
return diameter
left_height = self._height(node.get_left_child())
right_height = self._height(node.get_right_child())
left_diameter = self._diameter(node.get_left_child())
right_diameter = self._diameter(node.get_right_child())
return max(left_height + right_height + 1, max(left_diameter, right_diameter))"""
4
. .
3 5
. .
1 2
"""
tree = Tree()
tree.set_root(4)
tree.get_root().set_left_child(Node(3))
tree.get_root().set_right_child(Node(5))
tree.get_root().get_left_child().set_left_child(Node(1))
tree.get_root().get_left_child().set_right_child(Node(2))
ht = tree.height()
if ht == 3:
print('Yes, the height is 3.')
else:
print('Whoops, wrong height of {}, but should be 3.'.format(ht))
d = tree.diameter()
if d == 4:
print('Yes, the diameter is 4.')
else:
print('Whoops, wrong diameter of {}, but should be 4.'.format(ht))Here are the results from running this example:
Yes, the height is 3.
Yes, the diameter is 4.
"""
9
. .
8 10
. .
7 11
. .
6 5
.
4
. .
3 2
.
1
"""
tree = Tree()
tree.set_root(9)
tree.get_root().set_left_child(Node(8))
tree.get_root().set_right_child(Node(10))
tree.get_root().get_left_child().set_left_child(Node(7))
tree.get_root().get_right_child().set_right_child(Node(11))
tree.get_root().get_left_child().get_left_child().set_left_child(Node(6))
tree.get_root().get_left_child().get_left_child().set_right_child(Node(5))
tree.get_root().get_left_child().get_left_child().get_right_child().set_right_child(Node(4))
tree.get_root().get_left_child().get_left_child().get_right_child().get_right_child().set_left_child(Node(3))
tree.get_root().get_left_child().get_left_child().get_right_child().get_right_child().set_right_child(Node(2))
tree.get_root().get_left_child().get_left_child().get_right_child().get_right_child().get_right_child().set_right_child(Node(1))
ht = tree.height()
if ht == 7:
print('Yes, the height is 7.')
else:
print('Whoops, wrong height of {}, but should be 7.'.format(ht))
d = tree.diameter()
if d == 9:
print('Yes, the diameter is 9.')
else:
print('Whoops, wrong diameter of {}, but should be 9.'.format(ht))Here are the results from running this example:
Yes, the height is 7.
Yes, the diameter is 9.