Diagonal traversal of binary tree

Learn how to perform diagonal traversal of a binary tree.

Given a binary we have to print the elements at each node diagonally.

Example

Input
           1
	 /   \
        /     \
       2       3
      /      /  \
     /      /    \
    4      5      6
          / \
         /   \
        7     8

Output:
[1, 3, 6]
[2, 5, 8]
[4, 7]

We are going to see the two different solutions for it, recursive as well as iterative.

Recursively traverse the binary tree diagonally.

Conceptually this is how it works.

• Use a hashmap to store the list of elements at each diagonal.
• The element right to the current element will be at the same diagonal and on the left will be on the next diagonal.
• So call the function recursively with left and right element and diagonal number and keep storing the value in hashmap.

const printDiagonalRecursive = (root) => {
  //Hashmap
  const map = new Map();
  
  //Start the diagonal traversal 
  iterateDiagonal(root, 0, map);
  
  //Return the diagonal elements as multi dimensional array
  const arr = [];
  map.forEach((value) => {
      arr.push(value);
  });
  
  return arr;
}

const iterateDiagonal = (node, diagonal, map) => {
  //If empty node then terminate
  if(node === null){
    return;
  }
  
  //If there is no diagonal then create one and store the value in array or list.
  if(!map.has(diagonal)){
    map.set(diagonal, [node.val])
  }else{
    //Else If there is a diagonal already then push in its existing list.
    map.get(diagonal).push(node.val);
  }
  
  //Move to the next diagonal
  iterateDiagonal(node.left, diagonal + 1, map);
  
  //Move to the next element on same diagonal
  iterateDiagonal(node.right, diagonal, map);
}

Input:
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

const tree = new Node(8);  
tree.left = new Node(3);  
tree.right = new Node(10);  
tree.left.left = new Node(1);  
tree.left.right = new Node(6);  
tree.right.right = new Node(14);  
tree.right.right.left = new Node(13);  
tree.left.right.left = new Node(4);  
tree.left.right.right = new Node(7);

console.log(printDiagonalRecursive(tree));

Output:
[
  [8, 10, 14],
  [3, 6, 7, 13],
  [1, 4]
]

Time complexity: O(n).
Space complexity: O(n).

---

Iterative solution to perform the diagonal traversal of binary tree.

The approach remains the same as we have used in the recursive, the only difference is we are going to use queue to hold the nodes and track the diagonal with a dummy node.

const diagonalPrintIterative = (root) => {
  //Create a queue
  const q = [];
  
  //Create a dummy node to track if we have reached the end of the diagonal or not.
  const sentinal = new Node(-1);
  
  //Add all the nodes on the first diagonal to the queue.
  while(root !== null){
    q.unshift(root);
    root = root.right;
  }
  
  //Add the dummy node
  q.unshift(sentinal);
  
  //Track the elements of the diagonal
  const permanent = [];
  let temp = [];
  
  //Iterate the queue
  while(q.length !== 1){
    //Get the first node
    const front = q.pop();
    
    //If it is not dummy node then
    //Print all the values of that diagonal
    if(front.val !== sentinal.val){
      temp.push(front.val);
      
      //Add all the nodes of the next diagonal
      let node = front.left;
      while(node !== null){
        q.unshift(node);
        node = node.right;
      }
      
    }else{
      //Add the dummy node after each diagonal
      q.unshift(sentinal);
      permanent.push(temp);
      temp = [];
    }
  }
  
  //At the end add the elements of the last diagonal
  if(temp.length){
    permanent.push(temp);
  }
  
  //Return the elements
  return permanent;
}

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

const tree = new Node(8);  
tree.left = new Node(3);  
tree.right = new Node(10);  
tree.left.left = new Node(1);  
tree.left.right = new Node(6);  
tree.right.right = new Node(14);  
tree.right.right.left = new Node(13);  
tree.left.right.left = new Node(4);  
tree.left.right.right = new Node(7);

console.log(printDiagonalIterative(tree));

Output:
[
  [8, 10, 14],
  [3, 6, 7, 13],
  [1, 4]
]

Time complexity: O(n).
Space complexity: O(n).