Scale Engineer

Even Odd Tree

Med
#1479Time: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.Space: O(H), where H is the height of the tree. This space is used by the recursion stack and the `lastValues` list. In the worst case of a skewed tree, H can be equal to N (the number of nodes), leading to O(N) space complexity.
Algorithms
Breadth-First Search
Data structures
TreeBinary Tree

Prompt

A binary tree is named Even-Odd if it meets the following conditions:

  • The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
  • For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
  • For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

 

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 1 <= Node.val <= 106

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a recursive Depth-First Search (DFS) to traverse the tree. To enforce the ordering constraints (strictly increasing/decreasing) at each level, we need to keep track of the last value encountered at every level. A list can be used for this purpose, where the index corresponds to the tree level. A pre-order traversal ensures that nodes at a given level are processed from left to right.

Algorithm

  • Use a recursive helper function dfs(node, level).
  • Maintain a list, lastValues, where lastValues.get(level) stores the value of the previously visited node at that level.
  • The traversal must be pre-order (root, left, right) to ensure nodes at the same level are visited from left to right.
  • Base Case: If node is null, return true.
  • Parity Check:
    • If level is even, node.val must be odd. If not, return false.
    • If level is odd, node.val must be even. If not, return false.
  • Order Check:
    • If it's the first node at this level (i.e., level >= lastValues.size()), add its value to lastValues.
    • Otherwise, get prevVal = lastValues.get(level).
    • For an even level, check if node.val > prevVal. If not, return false.
    • For an odd level, check if node.val < prevVal. If not, return false.
    • If the check passes, update lastValues.set(level, node.val).
  • Recursive Step: Return true only if the recursive calls for both left and right children, dfs(node.left, level + 1) and dfs(node.right, level + 1), return true.

Walkthrough

We perform a pre-order traversal (root, left, right) of the tree. This ensures that for any given level, we visit the nodes from left to right. A helper function, say dfs(node, level), is used. It takes the current node and its level as arguments. We maintain a list, lastValues, accessible by the recursive calls, where lastValues.get(level) stores the value of the previously visited node at that level.

import java.util.ArrayList;import java.util.List; /** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    // List to store the last seen value at each level    private List<Integer> lastValues = new ArrayList<>();     public boolean isEvenOddTree(TreeNode root) {        return dfs(root, 0);    }     private boolean dfs(TreeNode node, int level) {        if (node == null) {            return true;        }         // Condition 1: Parity check based on level        // If level is even, value must be odd. If level is odd, value must be even.        // This is equivalent to checking if level and value have different parity.        if (level % 2 == node.val % 2) {            return false;        }         // Condition 2: Order check        // If this is the first node we've seen at this level        if (level >= lastValues.size()) {            lastValues.add(node.val);        } else {            int prevVal = lastValues.get(level);            // Even level: must be strictly increasing            if (level % 2 == 0) {                if (node.val <= prevVal) {                    return false;                }            }             // Odd level: must be strictly decreasing            else {                if (node.val >= prevVal) {                    return false;                }            }            // Update the last value for the current level            lastValues.set(level, node.val);        }         // Recurse for children        return dfs(node.left, level + 1) && dfs(node.right, level + 1);    }}

Complexity

Time

O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

Space

O(H), where H is the height of the tree. This space is used by the recursion stack and the `lastValues` list. In the worst case of a skewed tree, H can be equal to N (the number of nodes), leading to O(N) space complexity.

Trade-offs

Pros

  • Conceptually straightforward implementation of tree traversal.

Cons

  • Can cause a StackOverflowError for very deep trees due to the depth of recursion.

  • The space complexity depends on the tree's height, which can be O(N) for skewed trees, making it less memory-efficient in such cases compared to BFS.

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isEvenOddTree ( TreeNode root ) { Queue < TreeNode > que = new LinkedList < > (); que . add ( root ); que . add ( null ); int res = 1 ; int c = 0 ; int prev = 0 ; while (! que . isEmpty ()) { if ( res % 2 == 0 ) prev = Integer . MAX_VALUE ; else prev = Integer . MIN_VALUE ; while ( que . peek () != null ) { if ( que . peek (). val % 2 != res % 2 ) { return false ; } if ( res % 2 == 0 && prev <= que . peek (). val ) { return false ; } if ( res % 2 != 0 && prev >= que . peek (). val ) return false ; if ( que . peek (). left != null ) que . add ( que . peek (). left ); if ( que . peek (). right != null ) que . add ( que . peek (). right ); prev = que . poll (). val ; } que . poll (); if ( que . isEmpty ()) { break ; } res ++; que . add ( null ); } return true ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem