Diagonal Traversal of Binary Tree | A binary tree node ; root - root of the binary tree d - distance of current line from rightmost - topmost slope . diagonalPrint - multimap to store Diagonal elements ( Passed by Reference ) ; Base Case ; Store all nodes of same line together as a vector ; Increase the vertical distance if left child ; Vertical distance remains same for right child ; Print diagonal traversal of given binary tree ; Create a dict to store diagnoal elements ; Driver Program
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def diagonalPrintUtil ( root , d , diagonalPrintMap ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return NEW_LINE DEDENT try : NEW_LINE INDENT diagonalPrintMap [ d ] . append ( root . data ) NEW_LINE DEDENT except KeyError : NEW_LINE INDENT diagonalPrintMap [ d ] = [ root . data ] NEW_LINE DEDENT diagonalPrintUtil ( root . left , d + 1 , diagonalPrintMap ) NEW_LINE diagonalPrintUtil ( root . right , d , diagonalPrintMap ) NEW_LINE DEDENT def diagonalPrint ( root ) : NEW_LINE INDENT diagonalPrintMap = dict ( ) NEW_LINE diagonalPrintUtil ( root , 0 , diagonalPrintMap ) NEW_LINE print " Diagonal ▁ Traversal ▁ of ▁ binary ▁ tree ▁ : ▁ " NEW_LINE for i in diagonalPrintMap : NEW_LINE INDENT for j in diagonalPrintMap [ i ] : NEW_LINE INDENT print j , NEW_LINE DEDENT print " " NEW_LINE DEDENT DEDENT root = Node ( 8 ) NEW_LINE root . left = Node ( 3 ) NEW_LINE root . right = Node ( 10 ) NEW_LINE root . left . left = Node ( 1 ) NEW_LINE root . left . right = Node ( 6 ) NEW_LINE root . right . right = Node ( 14 ) NEW_LINE root . right . right . left = Node ( 13 ) NEW_LINE root . left . right . left = Node ( 4 ) NEW_LINE root . left . right . right = Node ( 7 ) NEW_LINE diagonalPrint ( root ) NEW_LINE