Alternating Parity Levels

Medium

You are given the root of a binary tree. Levels are numbered from zero: the root is level 0, its children are level 1, and so on. Call the tree alternating if: - on every even-numbered level, all values are odd and strictly increase from left to right; - on every odd-numbered level, all values are even and strictly decrease from left to right. Return True if the tree is alternating, and False otherwise.

Example 1

root=tree_node([7, 8, 2, 1, 5, None, 9]) → True

Level 0: [7], odd. Level 1: [8, 2], even and decreasing. Level 2: [1, 5, 9], odd and increasing. Everything fits.

Example 2

root=tree_node([3, 4, 6]) → False

Level 1 is even, but 4 then 6 goes up, while it must strictly go down.

Example 3

root=tree_node([2]) → False

The root sits on level 0, which needs odd values.

Constraints

The tree has between 1 and 10⁵ nodes
1 ≤ Node.val ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Breadth-First Search Binary Tree

Similar problems

Tree Rows by Depth Medium Snake Through the Tree Levels Medium Tree Levels From the Bottom Up Medium The Tree Seen From the Right Medium Tree Columns, Top Down Medium

Input

root=tree_node([7, 8, 2, 1, 5, None, 9])

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 136 tests on the server, hidden ones included.