## C# || How To Find Maximum Difference Between Node and Ancestor In Binary Tree Using C#

The following is a module with functions which demonstrates how to find the maximum difference between node and ancestor in binary tree using C#.

1. Max Ancestor Diff – Problem Statement

Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val – b.val| and a is an ancestor of b.

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

Example 1:

``` Input: root = [8,3,10,1,6,null,14,null,null,4,7,13] Output: 7 Explanation: We have various ancestor-node differences, some of which are given below : |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| = 3 Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7. ```

Example 2:

``` Input: root = [1,null,2,null,0,3] Output: 3 ```

2. Max Ancestor Diff – Solution

The following is a solution which demonstrates how to find the maximum difference between node and ancestor in binary tree.

``` 2. Max Ancestor Diff - Solution C# // ============================================================================ // Author: Kenneth Perkins // Date: Feb 14, 2023 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find maximum difference node and ancestor // ============================================================================ /** * 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 int MaxAncestorDiff(TreeNode root) { if (root == null) { return 0; } return Traverse(root, root.val, root.val); } public int Traverse(TreeNode node, int curMax, int curMin) { // if encounter leaves, return the max-min along the path if (node == null) { return curMax - curMin; } // else, update max and min // and return the max of left and right subtrees curMax = Math.Max(curMax, node.val); curMin = Math.Min(curMin, node.val); int left = Traverse(node.left, curMax, curMin); int right = Traverse(node.right, curMax, curMin); return Math.Max(left, right); } }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142 // ============================================================================//    Author: Kenneth Perkins//    Date:   Feb 14, 2023//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to find maximum difference node and ancestor// ============================================================================/** * 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 int MaxAncestorDiff(TreeNode root) {        if (root == null) {            return 0;        }        return Traverse(root, root.val, root.val);    }     public int Traverse(TreeNode node, int curMax, int curMin) {        // if encounter leaves, return the max-min along the path        if (node == null) {            return curMax - curMin;        }        // else, update max and min        // and return the max of left and right subtrees        curMax = Math.Max(curMax, node.val);        curMin = Math.Min(curMin, node.val);        int left = Traverse(node.left, curMax, curMin);        int right = Traverse(node.right, curMax, curMin);        return Math.Max(left, right);    }}// 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:

``` 7 3 ```

## C# || Two Sum IV – How To Get Two Numbers In Binary Search Tree Equal To Target Value Using C#

The following is a module with functions which demonstrates how to get two numbers in a binary search tree equal to target value using C#.

1. Find Target – Problem Statement

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

``` Input: root = [5,3,6,2,4,null,7], k = 9 Output: true ```

Example 2:

``` Input: root = [5,3,6,2,4,null,7], k = 28 Output: false ```

2. Find Target – Solution

The following are two solutions which demonstrates how to get two numbers in a binary search tree equal to target value.

Both solutions use a set to keep track of the items already seen.

Each time a new node is encountered, we subtract the target value from the current node value. If the difference amount from subtracting the two numbers exists in the set, a 2 sum combination exists in the tree

1. Recursive

The following solution uses Depth First Search when looking for the target value.

``` 2. Find Target - Solution - Recursive C# // ============================================================================ // Author: Kenneth Perkins // Date: Oct 9, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to get two numbers equal to target value // ============================================================================ public class Solution { public bool FindTarget(TreeNode root, int k) { return Traverse(root, k, new HashSet<int>()); } private bool Traverse(TreeNode node, int k, HashSet<int> seen) { if (node == null) { return false; } // Get remaining value var remaining = k - node.val; // Check if remaining value has been seen if (seen.Contains(remaining)) { return true; } // Add current node value to items seen seen.Add(node.val); // Keep traversing left and right looking for 2 sum return Traverse(node.left, k, seen) || Traverse(node.right, k, seen); } }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930 // ============================================================================//    Author: Kenneth Perkins//    Date:   Oct 9, 2022//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to get two numbers equal to target value// ============================================================================public class Solution {    public bool FindTarget(TreeNode root, int k) {        return Traverse(root, k, new HashSet<int>());    }     private bool Traverse(TreeNode node, int k, HashSet<int> seen) {        if (node == null) {            return false;        }        // Get remaining value        var remaining = k - node.val;         // Check if remaining value has been seen        if (seen.Contains(remaining)) {            return true;        }        // Add current node value to items seen        seen.Add(node.val);         // Keep traversing left and right looking for 2 sum        return Traverse(node.left, k, seen) || Traverse(node.right, k, seen);    }}// http://programmingnotes.org/ ```

2. Iterative

The following solution uses Breadth First Search when looking for the target value.

``` 2. Find Target - Solution - Iterative C# // ============================================================================ // Author: Kenneth Perkins // Date: Oct 9, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to get two numbers equal to target value // ============================================================================ public class Solution { public bool FindTarget(TreeNode root, int k) { if (root == null) { return false; } // Declare stack var stack = new Stack<TreeNode>(); // Keep track of values seen var seen = new HashSet<int>(); // Add root to stack stack.Push(root); // Loop through items on the stack while (stack.Count > 0) { // Get current node var node = stack.Pop(); // Get remaining value var remaining = k - node.val; // Check if remaining value has been seen if (seen.Contains(remaining)) { return true; } else { // Keep traversing left and right looking for 2 sum if (node.left != null) { stack.Push(node.left); } if (node.right != null) { stack.Push(node.right); } } // Add current node value to items seen seen.Add(node.val); } return false; } }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 // ============================================================================//    Author: Kenneth Perkins//    Date:   Oct 9, 2022//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to get two numbers equal to target value// ============================================================================public class Solution {    public bool FindTarget(TreeNode root, int k) {        if (root == null) {            return false;        }        // Declare stack        var stack = new Stack<TreeNode>();         // Keep track of values seen        var seen = new HashSet<int>();         // Add root to stack        stack.Push(root);         // Loop through items on the stack        while (stack.Count > 0) {            // Get current node            var node = stack.Pop();             // Get remaining value            var remaining = k - node.val;             // Check if remaining value has been seen            if (seen.Contains(remaining)) {                return true;            } else {                // Keep traversing left and right looking for 2 sum                if (node.left != null) {                    stack.Push(node.left);                }                if (node.right != null) {                    stack.Push(node.right);                }            }            // Add current node value to items seen            seen.Add(node.val);        }        return false;    }}// 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 ```

## C# || How To Traverse N-ary Tree Level Order Using C#

The following is a module with functions which demonstrates how to traverse a N-ary Tree level order using C#.

1. Level Order – Problem Statement

Given an n-ary tree, return the level order traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

``` Input: root = [1,null,3,2,4,null,5,6] Output: [[1],[3,2,4],[5,6]] ```

Example 2:

``` Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]] ```

2. Level Order – Solution

The following is a solution which demonstrates how to traverse a N-ary Tree level order.

This solution uses Breadth First Search to explore items at each level.

``` 2. Level Order - Solution C# // ============================================================================ // Author: Kenneth Perkins // Date: Sep 5, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to traverse a N-ary Tree Level Order // ============================================================================ /* // Definition for a Node. public class Node { public int val; public IList<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, IList<Node> _children) { val = _val; children = _children; } } */ public class Solution { public IList<IList<int>> LevelOrder(Node root) { var result = new List<IList<int>>(); if (root == null) { return result; } var queue = new Queue<Node>(); queue.Enqueue(root); while (queue.Count > 0) { var currentLevel = new List<int>(); for (int count = queue.Count - 1; count >= 0 ; --count) { var currentNode = queue.Dequeue(); currentLevel.Add(currentNode.val); foreach (var child in currentNode.children) { queue.Enqueue(child); } } result.Add(currentLevel); } return result; } }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 // ============================================================================//    Author: Kenneth Perkins//    Date:   Sep 5, 2022//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to traverse a N-ary Tree Level Order// ============================================================================/*// Definition for a Node.public class Node {    public int val;    public IList<Node> children;     public Node() {}     public Node(int _val) {        val = _val;    }     public Node(int _val, IList<Node> _children) {        val = _val;        children = _children;    }}*/public class Solution {    public IList<IList<int>> LevelOrder(Node root) {        var result = new List<IList<int>>();        if (root == null) {           return result;        }         var queue = new Queue<Node>();        queue.Enqueue(root);         while (queue.Count > 0) {            var currentLevel = new List<int>();            for (int count = queue.Count - 1; count >= 0 ; --count) {                var currentNode = queue.Dequeue();                currentLevel.Add(currentNode.val);                foreach (var child in currentNode.children) {                    queue.Enqueue(child);                }            }            result.Add(currentLevel);        }         return result;    }}// 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:

``` [[1],[3,2,4],[5,6]] [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]] ```

## C# || How To Validate A Binary Search Tree Using C#

The following is a module with functions which demonstrates how to validate a binary search tree using C#.

1. Is Valid BST – Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

``` Input: root = [2,1,3] Output: true ```

Example 2:

``` Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4. ```

2. Is Valid BST – Solution

The following is a solution which demonstrates how to validate a binary search tree.

``` 2. Is Valid BST - Solution C# // ============================================================================ // Author: Kenneth Perkins // Date: Aug 12, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to validate a BST // ============================================================================ /** * 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 IsValidBST(TreeNode root) { return Traverse(root, null, null); } private bool Traverse(TreeNode node, TreeNode min, TreeNode max) { if (node == null) { return true; } if (max != null && node.val >= max.val) { return false; } if (min != null && node.val <= min.val) { return false; } return Traverse(node.left, min, node) && Traverse(node.right, node, max); } }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839 // ============================================================================//    Author: Kenneth Perkins//    Date:   Aug 12, 2022//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to validate a BST// ============================================================================/** * 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 IsValidBST(TreeNode root) {        return Traverse(root, null, null);    }     private bool Traverse(TreeNode node, TreeNode min, TreeNode max) {        if (node == null) {            return true;        }        if (max != null && node.val >= max.val) {            return false;        }        if (min != null && node.val <= min.val) {            return false;        }        return Traverse(node.left, min, node)            && Traverse(node.right, node, max);    }}// 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 ```