CareerCup

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;
}

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

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;
    }

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