Diagonal traversal of a binary tree in Python

The problem is that given a binary tree we need to print all the elements diagonally. A binary tree is a type of tree with each internal node has at most two children, one left and one right. Tree traversal can be termed as the process of visiting each node of a tree and printing its value. There are several ways of traversing a tree. Some of them are pre-order traversal, post-order traversal, in-order traversal, etc. Apart from these, there can be many other ways of traversing a binary tree. Thus, the main goal of any traversing method is to inform the reader about the elements that are present in the binary tree. We will be focussing on the diagonal traversal of a binary tree in this article.

In this article, we are going to explore a different way of traversing a tree. That is we are going to traverse a tree diagonally. We will be traversing all the elements along a negative slope line. A negative slope line is a line that makes an angle of -45⁰ with the horizontal. That is each diagonal will be having a negative slope.

An example of diagonal traversal of a binary tree is as shown:

I have written an iterative code. This code uses a list to store diagonal elements. The running time complexity of the code is O(n). The logic for the given code is somewhat similar to that for the level order traversal of a binary tree. But there are some modifications that make it the diagonal traversal of a binary tree.

For writing the code a module named binarytree is used. This module is not available in the default set up of python as of now. Hence, this module can be installed by writing the following command on your PC’s command prompt:

pip install binarytree

Python Code: Diagonal traversal of a binary tree

#Python program for diagonal traversal of binary tree

#importing binarytree module for creating binary tree
from binarytree import Node

#function to print diagonal elements
def diagtrav(r):

#empty list to store diagonal elements
    d=[]

#Node to signal end of diagonal
    s=Node(-10)

#extracting the first diagonal
    while r:
        d.append(r)
        r=r.right

#appending signal node
    d.append(s)

#printing diagonals and side by side appending the next diagonal and printing till all diagonals are printed 
    while len(d)!=1:
        f=d.pop(0)
        if f!=s:
            print(f.value,end=' ')
            n=f.left
            while n:
                d.append(n)
                n=n.right
        else:
            d.append(s)
            print()

#Driver code
#creating a tree
r = Node(50) 
r.left = Node(55) 
r.right = Node(34) 
r.left.left = Node(65) 
r.left.right = Node(99) 
r.right.right = Node(31) 
r.right.right.left = Node(12) 
r.left.right.left = Node(7) 
r.left.right.right = Node(79)
r.left.right.right.left = Node(69)
r.left.right.right.right = Node(90)

print("Diagonal Traversal:")
#calling function to print diagonal traversal
diagtrav(r)

print()
print("Code By: YATHARTH JAIN")

OUTPUT:

Diagonal Traversal:
50 34 31 
55 99 79 90 12 
65 7 69 
Code By: YATHARTH JAIN