#include <iostream>

#include <map>

#include <queue>

#include <vector>

using namespace std;

// Structure to store a node

struct TreeNode {

int data;

TreeNode *left, *right;

TreeNode(int data)

{

this->data = data;

this->left = this->right = nullptr;

}

};

// Data Structure to store a doubly linked list node

struct ListNode {

vector<int> data;

ListNode *prev, *next;

ListNode(int data, ListNode* prev, ListNode* next)

{

(this->data).push_back(data);

this->prev = prev;

this->next = next;

}

ListNode(ListNode* prev, ListNode* next)

{

this->prev = prev;

this->next = next;

}

};

// Function to the stored in given doubly linked list

void print(ListNode* mid)

{

while (mid && mid->prev) {

mid = mid->prev;

}

for (int i: v)

cout << i << ‘ ‘;

cout << endl;

}

}

// Function to do a level-order traversal of the tree and determine

// the vertical order of given binary tree

// Each node of doubly linked list will store present at the

// corresponding vertical line in a binary tree

void updateDLLwithVerticalOrder(TreeNode* root, ListNode* curr)

{

// base case

if (root == nullptr)

return;

// create an empty queue for level order traversal and

// enqueue root node with its corresponding linked list node

queue<pair<TreeNode*, ListNode*>> q;

q.push(make_pair(root, curr));

// run till queue is not empty

while (!q.empty())

{

// pop front node from the queue

TreeNode* node = q.front().first;   // tree node

ListNode* curr = q.front().second;  // list node

q.pop();

// push value of current tree node to the corresponding list node

curr->data.push_back(node->data);

// process non-empty left child

if (node->left)

{

// create a new linked list node corresponding to the vertical line

// passing through node’s left child, if not already.

// This node would become prev pointer of current linked list node

if (!curr->prev) {

curr->prev = new ListNode(nullptr, curr);

}

// enqueue left child with its corresponding linked list node

q.push(make_pair(node->left, curr->prev));

}

// process non-empty right child

if (node->right)

{

// create a new linked list node corresponding to the vertical line

// passing through node’s right child, if not already.

// This node would become next pointer of current linked list node

if (!curr->next) {

curr->next = new ListNode(curr, nullptr);

}

// enqueue right child with its corresponding linked list node

q.push(make_pair(node->right, curr->next));

}

}

}

// Function to print nodes of a given binary tree in vertical order

void printVertical(TreeNode* root)

{

// create a linked list node corresponding to the vertical line through

// the root node

ListNode* curr = new ListNode(nullptr, nullptr);

// determine vertical order and store it in doubly linked list

updateDLLwithVerticalOrder(root, curr);

print(curr);

}

int main()

{

/* Construct below tree

1

/

/

2       3

/

/

5       6

/

/

7       8

/

/

9

*/

TreeNode* root = new TreeNode(1);

root->left = new TreeNode(2);

root->right = new TreeNode(3);

root->right->left = new TreeNode(5);

root->right->right = new TreeNode(6);

root->right->left->left = new TreeNode(7);

root->right->left->right = new TreeNode(8);

root->right->left->right->left = new TreeNode(9);

root->right->left->right->right = new TreeNode(10);

printVertical(root);

return 0;

}

SHARE