March 2024 – My Programming Notes

Monthly Archives: March 2024

C# || How To Determine If A Binary Tree Is Even Odd Tree Using C#

March 01, 2024 admin No comments

The following is a module with functions which demonstrates how to determine if a binary tree is an even odd tree using C#.

1. Is Even Odd Tree – Problem Statement

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.

2. Is Even Odd Tree – Solution

The following is a solution which demonstrates how to determine if a binary tree is an even odd tree.

This solution uses breadth-first search.





		
		
			2. Is Even Odd Tree - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine an even odd tree
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsEvenOddTree(TreeNode root) {
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        var isEvenLevel = true;
        while (queue.Count > 0) {
            int previousValue = isEvenLevel ? int.MinValue : int.MaxValue;
            for (var size = queue.Count - 1; size >= 0; --size) {
                var currentNode = queue.Dequeue();

                if (isEvenLevel) {
                    if (IsEven(currentNode.val) || previousValue >= currentNode.val) {
                        return false;
                    }
                } else {
                    if (!IsEven(currentNode.val) || previousValue <= currentNode.val) {
                        return false;
                    }
                }
                if (currentNode.left != null) {
                    queue.Enqueue(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.Enqueue(currentNode.right);
                }
                previousValue = currentNode.val;
            }
            isEvenLevel = !isEvenLevel;
        }
        return true;
    }

    private bool IsEven(int value) {
        return value % 2 == 0;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine an even odd tree
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsEvenOddTree(TreeNode root) {
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
 
        var isEvenLevel = true;
        while (queue.Count > 0) {
            int previousValue = isEvenLevel ? int.MinValue : int.MaxValue;
            for (var size = queue.Count - 1; size >= 0; --size) {
                var currentNode = queue.Dequeue();
 
                if (isEvenLevel) {
                    if (IsEven(currentNode.val) || previousValue >= currentNode.val) {
                        return false;
                    }
                } else {
                    if (!IsEven(currentNode.val) || previousValue <= currentNode.val) {
                        return false;
                    }
                }
                if (currentNode.left != null) {
                    queue.Enqueue(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.Enqueue(currentNode.right);
                }
                previousValue = currentNode.val;
            }
            isEvenLevel = !isEvenLevel;
        }
        return true;
    }
 
    private bool IsEven(int value) {
        return value % 2 == 0;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

true false false

Monthly Archives: March 2024

C# || How To Determine If A Binary Tree Is Even Odd Tree Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories