Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
why do we even need to perform reverse pre-order if at all we are using a linked list??
Does this mean, we just append the obejects to linklist on pre-order traversal and then update their right pointer as per requirement?
Any clarification is appreciated.
Try this
in inorder traversal ...
if the node has left child .......store the right child
make the right pointer point to the left child ....
traverse the whole right sub tree just formed to point the stored right child as right child
void modify(struct node *t){
if(t!=NULL){
modify(t->left);
struct node *temp;
if(t->left){
temp=t->right;
t->right=t->left;
while(t->right)
t=t->right;
t->right=temp;
}
modify(t->right);
}
}
private static Node transform(Node root) {
Node right = root.right;
Node rightMost = root;
if (root.left != null) {
rightMost = transform(root.left);
root.right = root.left;
root.left = null;
}
if (right == null) {
return rightMost;
}
rightMost.right = right;
rightMost = transform(right);
return rightMost;
}
It appeared too simple to need any explanation.
Here is the Approach:
One needs to make any left subtree, a right subtree.
If the node has just left child, then just moving the child to right will complete the processing for that node.
If there is a right child too, then it should be made right child of the right-most of the original left subtree.
The above function process a node, and then returns the rightmost node of the transformed subtree.
here my iterative solution in C++:
void transform_to_preorder_traversal() {
stack<Node*> s;
queue<Node*> path;
s.push(get_root());
while(!s.empty()) {
Node *n = s.top();
s.pop();
path.push(n);
if(n->right) {
s.push(n->right);
}
if(n->left) {
s.push(n->left);
}
}
bool init = true;
Node *prev = NULL;
while(!path.empty()) {
if(init) {
init = false;
prev = path.front();
path.pop();
}
Node *current = path.front();
prev->right = current;
path.pop();
prev = current;
}
}
simplified version in C++:
void transform_preorder_traversal() {
stack<Node*> s;
Node *prev = NULL;
bool init = true;
s.push(get_root());
while(!s.empty()) {
Node *n = s.top();
s.pop();
if(!init) {
prev->right = n;
}
prev = n;
path.push(n);
if(n->right) {
s.push(n->right);
}
if(n->left) {
s.push(n->left);
}
if(init) {
init = false;
}
}
Here's another recursive implementation in Java:
public Node<T> transformToRight(Node<T> node) {
if (node == null) {
return null;
}
if(node.left == null) {
return node;
}
Node<T> leftSubtree = transformToRight(node.left);
Node<T> rightSubtree = transformToRight(node.right);
// Move left subtree to the right of the current root
node.right = leftSubtree;
// Traverse the leftsubtree till the last node. And set right child as the right child of current root
while (leftSubtree.right != null)
leftSubtree = leftSubtree.right;
leftSubtree.right = rightSubtree;
return node;
}
The idea is like this:
1. For each node, we call transform on it's left and right node. As we do have to transform both the subtrees.
2. Once we have the left subtree and right subtree transformed, we add the left subtree in between the parent and the right subtree. Note, we have to set the parent.next = leftsubtreeroot, and traverse the left subtree till we reach the leaf, and set the next of that leaf to the parent.right
For the sentence "if(node.left==null){return node;}" I think the right subtree has not been transformed yet here, am I right?
for a tree like
1
/ \
2 3
\ \
4 5
/
6
The above code fails.. as mentioned above the postion of
(node.left== null)
check should be as shown below
TreeNode ChangeOrder(TreeNode node){
TreeNode leftree= null, rightree = null;
if(node==null)
return null;
leftree = ChangeOrder(node.left);
rightree = ChangeOrder(node.right);
if(node.left==null)
return node;
node.right = leftree;
while(leftree.right!=null)
leftree = leftree.right;
leftree.right = rightree;
return node;
}
Hi, i had a small bug in my code, all left pointers should be set to NULL...to make sure the tree is deleted correctly when calling the destructor of the tree...
void translate_preorder_traversal() {
stack<Node*> s;
Node *prev = NULL;
bool init = true;
s.push(get_root());
while(!s.empty()) {
Node *n = s.top();
s.pop();
if(!init) {
prev->left = NULL;
prev->right = n;
}
prev = n;
if(n->right) {
s.push(n->right);
}
if(n->left) {
s.push(n->left);
}
if(init) {
init = false;
}
}
void PreorderTraverse(queue<Node*>& myQueue, Node* head)
{
if (NULL == head)
{
return;
}
myQueue.push(head);
PreorderTraverse(myQueue, head->left);
PreorderTraverse(myQueue, head->right);
}
void Transform(Node*& head)
{
if (NULL == head)
{
return;
}
std::queue<Node*> myQueue;
PreorderTraverse(myQueue, head);
Node* pre = myQueue.front();
myQueue.pop();
head = pre;
while (!myQueue.empty())
{
Node* cur = myQueue.front();
myQueue.pop();
pre->right = cur;
pre->left = NULL;
pre = cur;
}
pre->right = NULL;
}
Recursive call to transform everything to a “Right” node.
public static void Transform(Node r)
{
if (r == null)
return;
if (r.Left != null)
Transform(r.Left);
if (r.Right != null)
Transform(r.Right);
if (r.Right != null )
{
if (r.Left != null)
{
RightMost(r).Right = r.Left;
r.Left = null;
}
}
else
{
if (r.Left != null)
{
r.Right = r.Left;
r.Left = null;
}
}
}
public static Node RightMost(Node n)
{
if (n==null)
return null;
while(n.Right != null)
{
n = n.Right;
}
return n;
}
void modify_subtree (tree *root, tree **new_ptr_addr)
{
tree *right = root->r_child;
root->r_child = root->l_child;
*new_ptr_addr = right;
}
tree **convert_to_preorder(tree *root)
{
if (root)
{
tree **left = convert_to_preorder(root->l_child);
tree **right = convert_to_preorder(root->r_child);
if (!left && !right)
{
return &(root->r_child);
}
if (left)
{
modify_subtree (root, left);
}
if (right)
{
return right;
}
else
{
return &(root->r_child);
}
}
return NULL;
}
idea is like:
for leaf node, address of right child is returned
for non-leaf node, if left subtree exist then it has returned a address that address should not point to right of this node & node's right should point to node's left.
if for non-leaf node, left subtree doesnot exist, do nothing/
for non-leaf node, if right subtree exist then this right subtree must have returned a address that address should be returned
for non-leaf node, if right subtree does not exist, then address of right child should be returned
this code can be trimmed more but with loss of clarity:
void modify_subtree (tree *root, tree *new_ptr_addr)
{
tree *right = root->r_child;
root->r_child = root->l_child;
new_ptr_addr->r_child = right;
}
tree *convert_to_preorder(tree *root)
{
if (root)
{
tree *left = convert_to_preorder(root->l_child);
tree *right = convert_to_preorder(root->r_child);
if (left)
{
modify_subtree (root, left);
}
if (right)
{
return right;
}
}
return root;
}
can anyone verify this for me
struct node
{
struct node* left;
struct node* right;
int num;
};
typedef struct node* tr;
tr pre(tr head)
{
tr cur = NULL,lf = NULL,ri = NULL,temp=NULL;
if(head==NULL)
return NULL;
lf = pre(head->left);
rf = pre(head->right);
if(head->left!=NULL)
{
if(head->right==NULL)
{
head->right = head->left;
head->left = NULL;
return head;
}
else
{
temp = head->left;
while(temp->right!=NULL)
temp = temp->right;
temp->right = head->right;
head->right=head->left;
head->left=NULL;
return rf;
}
}
if(head->right==NULL)
{
return head;
}
return head;
}
My function logic below might seem a little complicated at first but upon going through some test cases, you should be able to get it.
eg-
initial tree:
1
/ \
2 6
/ \
3 7
/ \
4 5
final tree:
1
\
2
\
3
\
4
\
5
\
6
\
7
static *var , c=1; //these two static variables are used to keep track of the actual root node
void modtree(root)
{
if (root==null)
return;
if (c==1) //upon first call, we get the root node and store it's location for later use
{
var=root;
c=0;
}
modtree (root->left); // an inorder traversal begins
if (root!=var) //if this current node is not the root node of the original tree
{
if (root->left!=null) // cases: where current node has only a left child or both left or right ch.
{
if(root->right=null) //only a left child: bring the child to right of the current node
{ root->right=root->left;
root->left=null;
}
else //both children of current node present
{
root->left->right=root->right; //make the right child , the right child of the left child of
//current node
root->right=root->left; //make the left child the right child of the current node
root->left=null;
}
}
}
else //case when the current node is the root node; when this step is
// reached, the left and right sub-trees of the root node will be right-
// aligned
{
tmp=root->left;
while(tmp->right!=null) // reach the last child of the left sub-tree
tmp=tmp->right;
tmp->right=root->right; //attach the right subtree of the root node to the right of the last
//child of left sub-tree
root->right=root->left; //make the left sub-tree the right child of the root node; we will
//have a degenerate right-aligned linked list. this is the final step.
root->left = null;
}
modtree(root->right);
}
in inorder traversal ...
if the node has left child .......store the right child
make the right pointer point to the left child ....
traverse the whole right sub tree just formed to point the stored right child as right child
void modify(struct node *t){
if(t!=NULL){
modify(t->left);
struct node *temp;
if(t->left){
temp=t->right;
t->right=t->left;
while(t->right)
t=t->right;
t->right=temp;
}
modify(t->right);
}
}
any thoughts ..??
public TreeNode modifyPointer(TreeNode root) {
if (root == null) {
return root;
}
else {
if (root.right == null) {
root.right = modifyPointer(root.left);
root.left = null;
return root;
}
else {
TreeNode temp = root.right;
root.right = modifyPointer(root.left);
TreeNode iter = root.right;
while (iter.right!=null) {
iter = iter.right;
}
iter.right = modifyPointer(temp);
root.left = null;
return root;
}
}
}
reverse preorder..
- Anonymous December 08, 2013right left root
prev=NULL
everytime acces the node set its right to prev
and prev=current
in the end we will have a sort of linked list whose 1 st element is root then left child then right,.,,
code is simple..
any thoughts???