Other Tree Traversals

1. Boundary Traversal
2. Diagonal Traversal

1. Boundary Traversal:

Boundary Traversal of a Tree includes:

• left boundary (nodes on left excluding leaf nodes)
• leaves (consist of only the leaf nodes)
• right boundary (nodes on right excluding leaf nodes)

Algorithm for Boundary Traversal:

BoundaryTraversal(tree)

• If root is not null:
  • Print root’s data
  • PrintLeftBoundary(root->left) // Print the left boundary nodes
  • PrintLeafNodes(root->left) // Print the leaf nodes of left subtree
  • PrintLeafNodes(root->right) // Print the leaf nodes of right subtree
  • PrintRightBoundary(root->right) // Print the right boundary nodes

Uses of Boundary Traversal:

• Boundary traversal helps visualize the outer structure of a binary tree, providing insights into its shape and boundaries.
• Boundary traversal provides a way to access and modify these nodes, enabling operations such as pruning or repositioning of boundary nodes.

2. Diagonal Traversal

In the Diagonal Traversal of a Tree, all the nodes in a single diagonal will be printed one by one.

Algorithm for Diagonal Traversal:

DiagonalTraversal(tree):

• If root is not null:
  • Create an empty map
  • DiagonalTraversalUtil(root, 0, M) // Call helper function with initial diagonal level 0
  • For each key-value pair (diagonalLevel, nodes) in M:
    • For each node in nodes:
    • Print node’s data

DiagonalTraversalUtil(node, diagonalLevel, M):

• If node is null:
• Return
• If diagonalLevel is not present in M:
  • Create a new list in M for diagonalLevel
• Append node’s data to the list at M[diagonalLevel]
• DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Traverse left child with increased diagonal level
• DiagonalTraversalUtil(node->right, diagonalLevel, M) // Traverse right child with same diagonal level

Uses of Diagonal Traversal:

• Diagonal traversal helps in visualizing the hierarchical structure of binary trees, particularly in tree-based data structures like binary search trees (BSTs) and heap trees.
• Diagonal traversal can be utilized to calculate path sums along diagonals in a binary tree.

Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. In this article, we will discuss about all the tree traversal techniques along with their uses.