Amazon Interview Question
Country: India
This does not work. Can you show the first call. I don't see any mechanism by which the original root's value will get switched to the new root. Your newParent's Parent, does not see newParent, as its child
Can't take of my previous comment, but I just overlooked an assignment. It works fine!!
public boolean dropTree(Node root,Node leafNode){
if(root.getNodeValue().equals(leafNode.getNodeValue())){
return true;
}
boolean isLeafNode = dropTree(root.getLeftNode(), leafNode);
if(isLeafNode){
dropLeftTree(root.getLeftNode(),root);
return isLeafNode;
}
isLeafNode = dropTree(root.getRightNode(), leafNode);
if(isLeafNode){
dropRightTree(root.getRightNode(),root);
return isLeafNode;
}
return false;
}
private void dropLeftTree(Node leftNode, Node root) {
leftNode.setRightNode(root);
root.setLeftNode(root.getRightNode());
root.setRightNode(null);
}
private void dropRightTree(Node rightNode, Node root) {
rightNode.setLeftNode(root);
root.setRightNode(root.getLeftNode());
root.setLeftNode(null);
}
// Take a non-trivial example
// 25
// 12 34
// 1 3 4 5
// if 3 is chosen The answer should be since the links wont change.
// 3
// 12
// 1 25
// 34
// 4 5
// 3's parent's parent becomes right child of 3's parent and this continues up untill root is reached and then stops.
public class BinaryTree<T>{
Node<T> root;
private Class Node<T>{
Node<T> left;
Node<T> right;
}
public BinaryTree<T> tiltUsingLeafNode(BinaryTree<T> tree, T leafNode){
Node<T> parent = findParent(leafNode);
return reverseParentRelationShip(root, parent);
}
}
The solution would be easier if there is a redundant parent link in each node along with left and right links.
Iam making tree structure in such a way where a Node has child as well as parent node associated with it.
reverseNode(Node node , Node initialLeafNode)
{
if(node.getChild() ==null)
{
return;
}
Node currentParent = node.getParent();
if(currentParent!=initialLeafNode)
{
node.setChild(currentParent);
}
currentNode.removeChild(node);
reverseTree(currentParent);
}
Here is my solution:
class TreeNode {
Object data;
TreeNode right;
TreeNode left;
TreeNode(Object data){
this.data = data;
}
}
boolean balance(TreeNode root, TreeNode holdingNode){
if(root.data == holdingNode.data){
return true;
}
if(root.left != null){
boolean dfsBalance = balance(root.left,holdingNode);
if(dfsBalance){
TreeNode left = root.left.right;
root.left.right = root;
root.left = left;
return true;
}
}
if(root.right != null){
boolean dfsBalance = balance(root.right,holdingNode);
if(dfsBalance){
TreeNode right = root.right.left;
root.right.left = root;
root.right = right;
return true;
}
}
return false;
}
a
/ \
b c
/ \ / \
d e f g
let's assume holding node: b
in this case the output will be:
b
/ \
d a
/ \
e c
/ \
f g
public Node hangFromALeaf(Node start, Node leaf) {
if (null == start || null == leaf) {
return null;
}
if (null == leaf.left && start == leaf && null == leaf.right) {
return leaf;
}
Node left = hangFromALeaf(start.left, leaf);
if (null != left) {
left.left = start;
start.right = start.left;
start.left = null;
return left;
}
Node right = handFromALeaf(start.right, leaf);
if (null != right) {
right.right = start;
start.left = start.right;
start.right = null;
return right;
}
return null;
}
if leaf comes from the left
we assign its parent to its left,
its parent's right will get the parent's left node (mirroring) and parent's
if leaf comes from right
we do the opposite,
propagate this logic till the root node, at the root node, we just switch the root's left with right (or vice versa depending on the location of the leaf) and we are done.
worst case nlog(n) to go down the tree logn to come up so i guess O(n) = nLog(n)
- GK June 07, 2014