## Amazon Interview Question for Backend Developers

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

We can solve it using recursion-
Algo-
1- if node is null return false;
2- if node have both left and right child then it will return true. (node + 2 child = 3 node (Odd number))
3- if node does not have any child then also it will return true. (node itself)
4- else it will return false.

``````boolean isCountOdd(Node root) {
if(root == null) {
return false;
}

boolean left = isCountOdd(root.left);
boolean left = isCountOdd(root.right);

if(left == right) {
return true;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````c =0
def count (node):
If node == None: c+= 1;return

count(node.left)
count(node.right)
count(root)
if c%2: return True
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I'll maintain a global variable "is_odd" which is modified by every node(by default the value is 1). If a node has both left and right nodes or (no nodes at all) then that node doesn't change the value of "is_odd" variable. But if a node has only a single child then it flips the global variable(i.e., o to 1 and 1 to 0).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class BinaryTree
{
public BinaryTreeNode Root;

public bool IsOdd()
{
return DFS(Root) == OddOrEven.Odd;
}

private OddOrEven DFS(BinaryTreeNode node)
{
if (node == null)
return OddOrEven.Even;

return DFS(node.Left) == DFS(node.Right) ? OddOrEven.Odd : OddOrEven.Even;
}

private enum OddOrEven
{
Odd,
Even
}
}

public class BinaryTreeNode
{
public int Number { get; set; }
public BinaryTreeNode Left;
public BinaryTreeNode Right;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````boolean isOdd(Node n) {
if(n==null)
return false;
boolean lOdd = isOdd(n.left);
boolean rOdd = isOdd(n.right);
return lOdd != rOdd;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.