Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: Even Odd Tree

Problem Statement

Given a binary tree, return true if it is an Even-Odd tree. Otherwise, return false.

The Even-odd tree must follow below two rules:

  1. At every even-indexed level (starting from 0), all node values must be odd and arranged in strictly increasing order from left to right.
  2. At every odd-indexed level, all node values must be even and arranged in strictly decreasing order from left to right.

Examples

Example 1

  • Input:
    1
   / \
  10  4
 / \
3   7
  • Expected Output: true

.....

.....

.....

Like the course? Get enrolled and start learning!
P

prakharpandeyvk

· 4 months ago

// much cleaner solution :


bool isEvenOddTree(TreeNode* root) {
        
        bool evenLevel = true;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int levelSize = q.size();
            int prev = evenLevel ? INT_MIN : INT_MAX;
            for(int i=0;i<levelSize;i++){
                TreeNode* curr = q.front();
                q.pop();
                cout<<evenLevel<<endl;
                cout<<curr->val<<endl;
                if(evenLevel){
                    if(curr->val %2 == 0 || curr->val <= prev)
                        return false;
                    
                }
                else{
                    if(curr->val%2 || curr->val >= prev)
                        return false;
                    
                }
Gaurav Thakur

Gaurav Thakur

· 2 days ago

Solution is storing all the level values in the list. Instead of storing all level values in the list, we can maintain the single int variable at level and compare the values with it while iterating on queue. And if at any point condition fails, it can return false.

public boolean isEvenOddTree(TreeNode root) {
        if(null == root) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int level = 0;
        while(!queue.isEmpty()) {

            int size = queue.size();
            int oldVal = 0;
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                if(level %2 == 0) {
                    if(node.val % 2 == 0 || (i > 0 && node.val <= oldVal))