Binary Tree Operations(III) - Convert a Binary Tree to Down-Right Representation | Bo's Blog
Left-Right representation of a binary tree is standard representation where every node has a pointer to left child and another pointer to right child.
Down-Right representation is an alternate representation where every node has a pointer to left (or first) child and another pointer to next sibling. So siblings at every level are connected from left to right.
Also check https://github.com/bo-yang/BinaryTree/blob/master/BinaryTree.h
Left-Right representation of a binary tree is standard representation where every node has a pointer to left child and another pointer to right child.
Down-Right representation is an alternate representation where every node has a pointer to left (or first) child and another pointer to next sibling. So siblings at every level are connected from left to right.
Given a binary tree in left-right representation as below
Convert the structure of the tree to down-right representation like the below tree.
A/ \B C/ \D E/ / \F G H
A |B – C |D — E |F — G – H
The conversion should happen in-place, i.e., left child pointer should be used as down pointer and right child pointer should be used as right sibling pointer.
The solution to this problem is (1) traversing this binary tree in layer order, (2)converting all nodes in the same layer as a single list and (3) connecting all the head nodes in each layer together.
In order to connecting layers together via heads, at the begining of each layer, we need to record the leftmost node as the head of this layer. And after traversing current layer, we also need to link the head of current layer to the head of next layer.
// An Iterative level order traversal based function to convert// left-right to down-right representation.void convert(node *root){ // Base Case if (root == NULL) return; queue<node *> q; q.push(root); node *firstnode = root; while (1) { // nodeCount (queue size) indicates number of nodes // at current lelvel. int nodeCount = q.size(); if (nodeCount == 0) break; node *prev = NULL; // Stores link of previously dequeued node. // Dequeue all nodes of current level and Enqueue all // nodes of next level while (nodeCount > 0) { // Dequeue a node and enqueue its children for next // iteration of outer loop node *node = q.front(); q.pop(); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); // If prev exists, then connect this node as right // sibling of prev. if (prev) { prev->right = node; // Since prev is not NULL, this is not the first node // of its level, so make the down (or left) pointer NULL node->left = NULL; } // If previous doesn't exist then link this node as down to // first node of previous level. And set the firstnode else { firstnode->left = node; firstnode = node; } // Update prev and nodecount prev = node; nodeCount--; } prev->right = NULL; // For last node in current level }}
TreeNode* Convert2DL(TreeNode* root) {
if(root==NULL)
return NULL;
queue<TreeNode*> q;
q.push(root);
int nCur=1; // number of nodes in current layer
TreeNode* head=NULL; // the head node in each layer
while(!q.empty()) {
head=q.front();
TreeNode* cur=head;
int nNext=0; // number of nodes in next layer
for(int i=0;i<nCur;++i) {
TreeNode* n=q.front();
q.pop();
if(n->left!=NULL) {
q.push(n->left);
nNext++;
}
if(n->right!=NULL) {
q.push(n->right);
nNext++;
}
// Link current node to the right of this layer
if(n!=head) {
cur->right=n;
cur=n;
cur->left=NULL;
}
}
nCur=nNext;
cur->right=NULL;
if(q.empty())
head->left=NULL;
else
head->left=q.front(); // point to the head of the next layer
}
return root;
}
Read full article from Binary Tree Operations(III) - Convert a Binary Tree to Down-Right Representation | Bo's Blog