Tag Archives: binary tree

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]
[]

C# || How To Determine Whether A Binary Tree Is A Symmetric Tree Using C#

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


1. Is Symmetric – Problem Statement

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Example 1


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

Example 2:

Example 2


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


2. Is Symmetric – Solution

The following is a solution which demonstrates how to determine whether a binary tree is a symmetric tree.

For two trees to be mirror images, the following three conditions must be true:


• 1 - Their root node's key must be same
• 2 - The left subtree of left tree and right subtree of right tree have to be mirror images
• 3 - The right subtree of left tree and left subtree of right tree have to be mirror images

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 Bottom Up Binary Tree Level Order Using C#

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


1. Level Order Bottom – Problem Statement

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

Example 1:

Example 1


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

Example 2:


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

Example 3:


Input: root = []
Output: []


2. Level Order Bottom – Solution

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

The idea of this solution is to have a result list which keeps track of the items found on each level. A variable is also used to keep track of the maximum depth levels in the tree. The max depth level is used to insert node values into their appropriate result list slot.

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:


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

C# || How To Get The Sum Of Binary Tree Nodes With Even Valued Grandparents Using C#

The following is a module with functions which demonstrates how to get the sum of binary tree nodes with even valued grandparents using C#.


1. Sum Even Grandparent – Problem Statement

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Example 1:

Example 1


Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Example 2:

Example 2


Input: root = [1]
Output: 0


2. Sum Even Grandparent – Solution

The following is a solution which demonstrates how to get the sum of binary tree nodes with even valued grandparents.

The idea of this solution is to simply traverse the tree, and for each recursive call, we keep track of the parent node and the grandparent node of each node.

If a node has a grandparent, we check to see if it is an even number. If it is, the result is incremented.

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:


18
0

C# || How To Get The Number Of Binary Tree Paths Equal To Path Sum Using C#

The following is a module with functions which demonstrates how to get the number of binary tree paths equal to path sum using C#.


1. Number Of Path Sum Paths – Problem Statement

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Example 1


Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:


Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3


2. Number Of Path Sum Paths – Solution

The following is a solution which demonstrates how to get the number of binary tree paths equal to path sum.

The main idea here is that the sum at each level for each path is calculated. When the next level is explored, the value at the previous level is summed together with the node value at the current level.

A map dictionary is used to keep track of the sum at each level. If the prefix sum at the previous level is enough to equal the target path sum at the current level, the result count is incremented.

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
3

C# || How To Get All Root To Leaf Binary Tree Paths Equal To Path Sum Using C#

The following is a module with functions which demonstrates how to get all the root to leaf binary tree paths equal to path sum using C#.


1. Root To Leaf Path Sum – Problem Statement

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Example 1


Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Example 2


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

Example 3:


Input: root = [1,2], targetSum = 0
Output: []


2. Root To Leaf Path Sum – Solution

The following is a solution which demonstrates how to get all the root to leaf binary tree paths equal to path sum.

The main idea here is that the sum at each level for each path is calculated until we reach the end of the root-to-leaf.

A list is used to store the node value at each level. When the next level is explored, the value is appended to the list, and the process continues.

When we reach the end of the leaf, we check to see if the target value has been reached. If so, we add the node values that make up the path to the result list.

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:


[[5,4,11,2],[5,8,4,5]]
[]
[]

C# || How To Determine If Binary Tree Root To Leaf Path Sum Exists Using C#

The following is a module with functions which demonstrates how to determine if a binary tree root to leaf path sum exists using C#.


1. Has Path Sum – Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Example 1


Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

Example 2:

Example 2


Input: root = [1,2,3], targetSum = 5
Output: false

Example 3:


Input: root = [1,2], targetSum = 0
Output: false


2. Has Path Sum – Solution

The following is a solution which demonstrates how to determine if a binary tree root to leaf path sum exists.

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

C# || How To Convert Sorted Array to Binary Search Tree Using C#

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


1. Sorted Array To BST – Problem Statement

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

Example 1


Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 1

Example 2:

Example 2


Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.


2. Sorted Array To BST – Solution

The following is a solution which demonstrates how to convert a sorted array to 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:


[0,-10,5,null,-3,null,9]
[1,null,3]