Amazon Interview Question
Backend DevelopersCountry: United States
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).
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;
}
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.
- azambhrgn April 04, 2019