Tag Archives: binary tree

C# || Parallel Courses III – How To Find Minimum Number Months To Complete All Courses Using C#

The following is a module with functions which demonstrates how to find the minimum number of months needed to complete all courses using C#.


1. Minimum Time – Problem Statement

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCoursej, nextCoursej] denotes that course prevCoursej has to be completed before course nextCoursej (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)th course.

You must find the minimum number of months needed to complete all the courses following these rules:

  • You may start taking a course at any time if the prerequisites are met.
  • Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

Example 1:


Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output: 8
Explanation: The figure above represents the given graph and the time required to complete each course.
We start course 1 and course 2 simultaneously at month 0.
Course 1 takes 3 months and course 2 takes 2 months to complete respectively.
Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

Example 2:


Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output: 12
Explanation: The figure above represents the given graph and the time required to complete each course.
You can start courses 1, 2, and 3 at month 0.
You can complete them after 1, 2, and 3 months respectively.
Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.
Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.
Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.


2. Minimum Time – Solution

The following is a solution which demonstrates how to find the minimum number of months needed to complete all courses.

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:


8
12

C# || How To Find Largest Value In Each Binary Tree Row Using C#

The following is a module with functions which demonstrates how to find the largest value in each binary tree row using C#.


1. Largest Values – Problem Statement

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:


Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Example 2:


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


2. Largest Values – Solution

The following is a solution which demonstrates how to find the largest value in each binary tree row.

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,9]
[1,3]

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:

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:

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.

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:

Example 1


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

Example 2:

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. Iterative

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

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:

Example 1


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

Example 2:

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.

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:

Example 1


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

Example 2:

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.

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# || Binary Tree Right Side View – How To Get Nodes Ordered Top To Bottom C#

The following is a module with functions which demonstrates how to get nodes in a binary tree ordered from top to bottom using C#.


1. Right Side View – Problem Statement

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Example 1


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

Example 2:


Input: root = [1,null,3]
Output: [1,3]

Example 3:


Input: root = []
Output: []


2. Right Side View – Solution

The following is a solution which demonstrates how to get right side nodes ordered from top to bottom.

This solution uses Depth First Search level order traversal to explore items at each level, and then adds the last node on every layer.

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,4]
[1,3]
[]

C# || How To Get Total Sum Root To Leaf Binary Numbers In Binary Tree Using C#

The following is a module with functions which demonstrates how to get the total sum root to leaf binary numbers in a binary tree using C#.


1. Sum Root To Leaf – Problem Statement

You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.

  • For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

The test cases are generated so that the answer fits in a 32-bits integer.

A leaf node is a node with no children.

Example 1:

Example 1


Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Example 2:


Input: root = [0]
Output: 0


2. Sum Root To Leaf – Solution

The following is a solution which demonstrates how to get the total sum root to leaf binary numbers in a binary tree.

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

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:


22
0

C# || How To Construct Binary Tree From Preorder And Inorder Traversal Using C#

The following is a module with functions which demonstrates how to construct a binary tree from pre order and in order traversal using C#.


1. Build Tree – Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Example 1


Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:


Input: preorder = [-1], inorder = [-1]
Output: [-1]


2. Build Tree – Solution

The following is a solution which demonstrates how to construct a binary tree from pre order and in order traversal.

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:


[3,9,20,null,null,15,7]
[-1]

C# || How To Construct Binary Tree From Inorder And Postorder Traversal Using C#

The following is a module with functions which demonstrates how to construct a binary tree from in order and post order traversal using C#.


1. Build Tree – Problem Statement

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Example 1


Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:


Input: inorder = [-1], postorder = [-1]
Output: [-1]


2. Build Tree – Solution

The following is a solution which demonstrates how to construct a binary tree from in order and post order traversal.

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:


[3,9,20,null,null,15,7]
[-1]

C# || How To Get Total Sum Of Left Leaves In Binary Tree Using C#

The following is a module with functions which demonstrates how to get the total sum of left leaves in a binary tree using C#.


1. Sum Of Left Leaves – Problem Statement

Given the root of a binary tree, return the sum of all left leaves.

A leaf node is a node with no children.

Example 1:

Example 1


Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2:


Input: root = [1]
Output: 0


2. Sum Of Left Leaves – Solution

The following are two solutions which demonstrates how to get the total sum of left leaves in a binary tree.

Both solutions use Depth First Search to explore items at each level.

In both solutions, we traverse the left and right side of the tree, keeping track of which node is the ‘left’ node.

When a leaf is encountered and its a node on the left side, we increment the final result with the value of the node on the left side.

Recursive

Iterative

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:


24
0

C# || How To Get Total Sum Root To Leaf Numbers In Binary Tree Using C#

The following is a module with functions which demonstrates how to get the total sum root to leaf numbers in a binary tree using C#.


1. Sum Numbers – Problem Statement

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

  • For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

Example 1


Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Example 2


Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.


2. Sum Numbers – Solution

The following are two solutions which demonstrates how to get the total sum root to leaf numbers in a binary tree.

Both solutions use Depth First Search to explore items at each level.

Recursive

Iterative

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:


25
1026

C# || How To Traverse Binary Tree Level Order Using C#

The following is a module with functions which demonstrates how to traverse binary tree level order using C#.


1. Level Order – Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Example 1


Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:


Input: root = [1]
Output: [[1]]

Example 3:


Input: root = []
Output: []


2. Level Order – Solution

The following is a solution which demonstrates how to traverse binary tree level order.

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

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:


[[3],[9,20],[15,7]]
[[1]]
[]

C# || How To Invert Binary Tree Using C#

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


1. Invert Tree – Problem Statement

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Example 1


Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Example 2


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

Example 3:


Input: root = []
Output: []


2. Invert Tree – Solution

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

An inverted Binary Tree is simply a Binary Tree whose left and right children are swapped.

This solution:

  • Traverses the left subtree
  • Traverses the right subtree
  • When both trees have been traversed, swap left and right child subtrees

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:


[4,7,2,9,6,3,1]
[2,3,1]
[]