Amazon Interview Question
SDE-3sTeam: Amazon Fresh
Country: United States
Interview Type: Phone Interview
Assum root of the tree is given, you can do recursive in-order call to right and left subtrees and get the sum.
sumTree(struct tree* node, int *sum) {
if(node == NULL) {
return;
}
/* Do in order traversal */
sumTree(node->left, sum);
*sum = *sum + node->data;
sumTree(node->right, sum);
}
int main() {
int rightSum = 0;
int leftSum = 0;
sumTree(root->left, &leftSum);
sumTree(root->right, &rightSum);
if(leftSum == rightSum) {
printf("Tree is balanced \n");
}else {
printf("Tree not balanced \n");
}
}
I think the allBalancedNodes() can be achieved in O(n) with post Order traversal.
Have a variable called total in the node like below:
class Node
{
int total; // -- a variable indicating sum seen until now
int key;
int value;
Node left;
Node right;
Node parent;
}
isBalanced() definition:
public boolean isBalanced()
{
return ( ( left == null && right == null ) || ( left != null && right != null && left.total == right.total ) );
}
Post order traversal updating total on each node :
public void postOrderTraversal( Node node )
{
if ( node == null ) return;
postOrderTraversal( node.left );
postOrderTraversal( node.right );
node.total = node.value;
if ( node.left != null ) node.total += node.left.total;
if ( node.right != null ) node.total += node.right.total;
System.out.println( " Is balanced : " + node.isBalanced() );
}
import java.util.List;
import java.util.Queue;
import java.util.ArrayList;
import java.util.LinkedList;
public class BalanceSumBinaryTree
{
public static void main(String[] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(1);
root.right.left = new TreeNode(1);
BalanceSumBinaryTree b = new BalanceSumBinaryTree();
System.out.println(b.isBalance(root));
System.out.println(b.allBalanceNodes(root));
}
public boolean isBalance(TreeNode root)
{
if(root==null)
return true;
int left = helper(root.left);
int right = helper(root.right);
return left==right;
}
private int helper(TreeNode root)
{
if(root==null)
return 0;
int left = helper(root.left);
int right = helper(root.right);
return left + root.val + right;
}
public List<TreeNode> allBalanceNodes(TreeNode root)
{
Queue<TreeNode> next = new LinkedList<>();
Queue<TreeNode> curr;
next.offer(root);
List<TreeNode> res = new ArrayList<>();
while(!next.isEmpty())
{
curr = next;
next = new LinkedList<>();
while(!curr.isEmpty())
{
TreeNode temp = curr.poll();
if(isBalance(temp))
res.add(temp);
if(temp.left!=null)
next.offer(temp.left);
if(temp.right!=null)
next.offer(temp.right);
}
}
return res;
}
}
class TreeNode
{
int val;
TreeNode left;
TreeNode right;
TreeNode(int val)
{
this.val = val;
}
public String toString()
{
return this.val+" ";
}
}
This is easy one, Same as height balance.
- hprem991 August 14, 2017Rather than increment by 1, you have to increment by the node->data