Find node having max value in a binary tree.
**Binary Tree Constraint:** Each node contains a distinct natural number in such a way that, at each odd level, left child is smaller than the immediate parent node and right child is greater than the immediate parent node. Vice-versa at even level. That is at each even level, left child is greater than the immediate parent node and right child is smaller than the immediate parent node.Also, suppose that level starts with 1. I have been asked this in a interview.

My Solution: BFS traverse the binary tree and find the max value. I know this is not optimal solution but, interviewer wants the optimized solution. 

class TreeNode{

```
int data;
TreeNode left, right;

TreeNode(int data) {
    this.data = data;
    this.left = null;
    this.right = null;
}

int findMax(TreeNode root) {
    if (root == null) {
        return -1;
    }
    int max = root.data;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while (queue.size() != 0) {
        TreeNode node = queue.poll();
        if (node.data > max) {
            max = node.data;
        }
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    return max;
}

public static void main(String[] args) {
    TreeNode newNode = new TreeNode(6);
    newNode.left = new TreeNode(3);
    newNode.right = new TreeNode(7);
    newNode.left.left = new TreeNode(10);
    newNode.left.right = new TreeNode(2);
    newNode.right.left = new TreeNode(8);
    newNode.right.right = new TreeNode(5);
    int maxValue = newNode.findMax(newNode);
    System.out.println(maxValue);
}

```

}