Boundary traversal of a tree in Python
By Prashanth Gowda R SIn this tutorial, we will learn to traverse all the boundary nodes of a binary tree in Python. We will append all the boundary nodes of the tree to a list in the anti-clockwise direction starting from the root node. Boundary traversal of a tree can be divided into three divisions. Traverse the left boundary nodes, leaf nodes, and the right boundary nodes.
Let’s create the above binary tree in Python and learn to traverse its boundary nodes in the anti-clockwise direction.
class Tree:
Traversal = []
def __init__(node,value):
node.value = value
node.right = None
node.left = None
def create_node(node,value):
if (node.value is None):
node.value = value
else:
if( value < node.value ):
if (node.left is None):
node.left = Tree(value)
else:
node.left.create_node(value)
elif( value > node.value ):
if ( node.right is None):
node.right = Tree(value)
else:
node.right.create_node(value)
Root = Tree(4)
Root.create_node(6)
Root.create_node(8)
Root.create_node(5)
Root.create_node(2)
Root.create_node(3)
Root.create_node(7)
Root.create_node(1)
Boundary Traversal in Python
At first, we will learn to traverse all the left boundary nodes of the binary tree. Starting from the root node and excluding the left leaf node.
def Left_nodes(node,Root):
if(Root is None):
return
if (Root.left):
Tree.Traversal.append(Root.value)
node.Left_nodes(Root.left)
elif(Root.right):
Tree.Traversal.append(Root.value)
node.Left_nodes(Root.right)- If the root node is not empty, the root node is added to the list ‘Traversal’ and its left boundary nodes are traversed.
- If a boundary node doesn’t have a left child, it will look for the right child. The right node is added to the list and its left boundary nodes are traversed.
- The above snippet of code inserts the left boundary nodes( 2, 4) to the list. Excluding the leaf node.
Now, we have to traverse all the leaf nodes of the tree. However, we excluded the left leaf node while traversing the left boundary nodes to ensure no duplicate nodes.
def Leaf_nodes(node,Root):
if(Root is None):
return
node.Leaf_nodes(Root.left)
if Root.left is None and Root.right is None:
Tree.Traversal.append(Root.value)
node.Leaf_nodes(Root.right)- We know that the leaf nodes don’t have any child.
- Traverse left nodes till the last, where the left and right child of the node is None and add that node to the list.
- Similarly, traverse the right nodes till the last( leaf node) and add that node to the list.
- The above code snippet inserts the leaf nodes( 1, 3, 5, 7) to the list.
At this movement, we have traversed the left boundary nodes including the root node and the leaf nodes. Now, we have to traverse the right boundary nodes excluding the root node and the right leaf node. Also, we have to traverse in the reverse direction. That is, from the leaf node to the root node.
def Right_nodes(node,Root):
if(Root is None):
return
if (Root.right):
node.Right_nodes(Root.right)
Tree.Traversal.append(Root.value)
elif(Root.left):
node.Right_nodes(Root.left)
Tree.Traversal.append(Root.value)
- While the node is not empty and it has a right child, traverse to the right nodes. Add that node to the list.
- If the node doesn’t have the right child but it has the left child, traverse to the left node and add the node to the list ‘Traversal’.
- Therefore, the above code snippet inserts the right boundary nodes( 8, 6) to the list.
Hence the expected output of the boundary traversal algorithm is [4, 2, 1, 3, 5, 7, 8, 6 ].
Here is how the complete code should look like
class Tree:
Traversal = []
def __init__(node,value):
node.value = value
node.right = None
node.left = None
def create_node(node,value):
if (node.value is None):
node.value = value
else:
if( value < node.value ):
if (node.left is None):
node.left = Tree(value)
else:
node.left.create_node(value)
elif( value > node.value ):
if ( node.right is None):
node.right = Tree(value)
else:
node.right.create_node(value)
def Left_nodes(node,Root):
if(Root is None):
return
if (Root.left):
Tree.Traversal.append(Root.value)
node.Left_nodes(Root.left)
elif(Root.right):
Tree.Traversal.append(Root.value)
node.Left_nodes(Root.right)
def Leaf_nodes(node,Root):
if(Root is None):
return
node.Leaf_nodes(Root.left)
if Root.left is None and Root.right is None:
Tree.Traversal.append(Root.value)
node.Leaf_nodes(Root.right)
def Right_nodes(node,Root):
if(Root is None):
return
if (Root.right):
node.Right_nodes(Root.right)
Tree.Traversal.append(Root.value)
elif(Root.left):
node.Right_nodes(Root.left)
Tree.Traversal.append(Root.value)
Root = Tree(4)
Root.create_node(6)
Root.create_node(8)
Root.create_node(5)
Root.create_node(2)
Root.create_node(3)
Root.create_node(7)
Root.create_node(1)
Root.Left_nodes(Root)
Root.Leaf_nodes(Root)
Root.Right_nodes(Root.right)
print(Tree.Traversal)
Output:
[4, 2, 1, 3, 5, 7, 8, 6]
I hope you have understood the code…😊
If you have any quires, please feel free to drop in your comments.
You may also read different tree traversal algorithms:
- Inorder traversal in Python.
- Preorder traversal in Python.
- Postorder traversal in Python.
- Level order traversal in Python.
- Spiral order traversal in Python.
Thank you..!
hi, can you drop a code of diagonal traversal please? this is the best code I’ve found