DAY 55 - Traversals in a Binary Tree Part 2

Welcome to DAY 55. Today we will diverge once again into the Data Structure Trees and look at some more traversals. I suggest reading the previous article on Trees before reading this.
Content Credits

Level Order Traversal:

The level order traversal of this is : [1,[2,3],[4,5,6,7]]

Imagine dividing the tree into levels.
Root node being level 0.
Every time the tree has a child(either left or right) it extends it's level by one.
You can also understand this as a breadth wise traversal of the tree.
In level order traversal, each node is visited level-wise in increasing order of levels from left to right.

Algorithm and Code:

• Initialize a queue of Node* type.
• Visit the root and add into queue.
• While traversing that node, add the elements of next level into the queue and pop the previous level.
• Before popping each level , we store the node value into our temp array.
• We push back temp array into our result after every level.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL){
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int size = q.size();
            vector<int> temp;
            for(int i = 0;i < size; i++){
                TreeNode *node = q.front();
                q.pop();
                if(node->left != NULL) q.push(node->left);
                if(node->right != NULL) q.push(node->right);
                temp.push_back(node->val);
            }
            res.push_back(temp);
        }
        return res;
    }
};

Vertical Order Traversal

A vertical order traversal is a traversal where we view the binary trees in terms of coloumns.
Left being the most negative , root node being in the coloumn 0 and the right most being the most positive.

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]

Algorithm:

• The algorithm uses a map called nodes to store the nodes of the binary tree grouped by their vertical and horizontal positions. The keys of the map are the vertical positions (x), and the values are inner maps, where the keys represent the level (y) of the nodes, and the values are multiset data structures containing the nodes' values at each vertical level.

• To perform the vertical traversal, a queue is initialized, and the root node is enqueued with initial vertical position 0 and level 0.

• The node's value is inserted into the multiset corresponding to its vertical and level positions and update the value of vertical to a positive addition or negative addition on the basis of left or right.

• After the traversal is complete, the nodes map contains the binary tree nodes grouped by their vertical and level positions.

• The nodes' values are extracted from the nodes map and added to the ans vector. The nodes are inserted column-wise (vertical order) in ascending order of levels.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    vector<vector<int>> verticalTraversal(TreeNode* root) {
         map < int, map < int, multiset < int >>> nodes;
  queue < pair < TreeNode * , pair < int, int >>> q;
  q.push({root,{0,0}});
   //initial vertical and level
  while (!q.empty()) {
    auto p = q.front();
    q.pop();
    TreeNode * node = p.first;

    //x -> vertical , y->level
    int x = p.second.first, y = p.second.second;
    nodes[x][y].insert(node -> val); //inserting to multiset

    if (node -> left) q.push({node->left,{x-1,y+1}});
    if (node -> right) q.push({node->right,{x+1,y+1}});
  }
  vector < vector < int >> ans;
  for (auto it: nodes) {
    vector < int > tempArray;
    for (auto q: it.second) {
      tempArray.insert(tempArray.end(), q.second.begin(), q.second.end());
    }
    ans.push_back(tempArray);
  }
  return ans;
}
};

Thanks for reading. I will be back with some more tree content.