November 3, 2021 – My Programming Notes

Daily Archives: November 3, 2021

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

November 03, 2021 admin No comments

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:

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





		
		
			2. Sum Of Left Leaves - Recursive - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 3, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get the sum of left leaves
// ============================================================================
/**
 * 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 SumOfLeftLeaves(TreeNode root) {
        return Traverse(root, false);
    }

    private int Traverse(TreeNode node, bool isLeft) {
        if (node == null) {
            return 0;
        }
        // We have reached a leaf node
        if (node.left == null && node.right == null) {
            return isLeft ? node.val : 0;
        }
        // Keep traversing left and right looking for left leaves
        return Traverse(node.left, true) + Traverse(node.right, false);
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 3, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get the sum of left leaves
// ============================================================================
/**
 * 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 SumOfLeftLeaves(TreeNode root) {
        return Traverse(root, false);
    }
 
    private int Traverse(TreeNode node, bool isLeft) {
        if (node == null) {
            return 0;
        }
        // We have reached a leaf node
        if (node.left == null && node.right == null) {
            return isLeft ? node.val : 0;
        }
        // Keep traversing left and right looking for left leaves
        return Traverse(node.left, true) + Traverse(node.right, false);
    }
}// http://programmingnotes.org/

Iterative





		
		
			2. Sum Of Left Leaves - Iterative - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 3, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get the sum of left leaves
// ============================================================================
/**
 * 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 SumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // Declare stack
        var stack = new Stack<KeyValuePair<TreeNode, bool>>();
        var result = 0;

        // Add root to stack
        stack.Push(new KeyValuePair<TreeNode, bool>(root, false));

        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node and value indicating if its a left node
            var current = stack.Pop();
            var node = current.Key;
            var isLeft = current.Value;

            // We have reached a leaf node
            if (node.left == null && node.right == null) {
                result += isLeft ? node.val : 0;
            } else {
                // Keep traversing left and right looking for left leaves
                if (node.left != null) {
                    stack.Push(new KeyValuePair<TreeNode, bool>(node.left, true));
                }
                if (node.right != null) {
                    stack.Push(new KeyValuePair<TreeNode, bool>(node.right, false));
                }
            }
        }

        return result;
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 3, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get the sum of left leaves
// ============================================================================
/**
 * 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 SumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // Declare stack
        var stack = new Stack<KeyValuePair<TreeNode, bool>>();
        var result = 0;
 
        // Add root to stack
        stack.Push(new KeyValuePair<TreeNode, bool>(root, false));
 
        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node and value indicating if its a left node
            var current = stack.Pop();
            var node = current.Key;
            var isLeft = current.Value;
 
            // We have reached a leaf node
            if (node.left == null && node.right == null) {
                result += isLeft ? node.val : 0;
            } else {
                // Keep traversing left and right looking for left leaves
                if (node.left != null) {
                    stack.Push(new KeyValuePair<TreeNode, bool>(node.left, true));
                }
                if (node.right != null) {
                    stack.Push(new KeyValuePair<TreeNode, bool>(node.right, false));
                }
            }
        }
 
        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:

24 0

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

November 03, 2021 admin No comments

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:

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:

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





		
		
			2. Sum Numbers - Recursive - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 3, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get sum root to leaf numbers
// ============================================================================
/**
 * 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 SumNumbers(TreeNode root) {
        return Traverse(root, 0);
    }

    private int Traverse(TreeNode node, int currentSum) {
        if (node == null) {
            return 0;
        }

        // Calculate current sum
        currentSum = (currentSum * 10) + node.val;

        // We have reached a leaf node
        if (node.left == null && node.right == null) {
            return currentSum;
        }

        // Keep traversing left and right calculating the sum
        return Traverse(node.left, currentSum) + Traverse(node.right, currentSum);
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 3, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get sum root to leaf numbers
// ============================================================================
/**
 * 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 SumNumbers(TreeNode root) {
        return Traverse(root, 0);
    }
 
    private int Traverse(TreeNode node, int currentSum) {
        if (node == null) {
            return 0;
        }
 
        // Calculate current sum
        currentSum = (currentSum * 10) + node.val;
 
        // We have reached a leaf node
        if (node.left == null && node.right == null) {
            return currentSum;
        }
 
        // Keep traversing left and right calculating the sum
        return Traverse(node.left, currentSum) + Traverse(node.right, currentSum);
    }
}// http://programmingnotes.org/

Iterative





		
		
			2. Sum Numbers - Iterative - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 3, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get sum root to leaf numbers
// ============================================================================
/**
 * 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 SumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // Declare stack
        var stack = new Stack<KeyValuePair<TreeNode, int>>();
        var result = 0;

        // Add root to stack
        stack.Push(new KeyValuePair<TreeNode, int>(root, 0));

        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node and running sum
            var current = stack.Pop();
            var node = current.Key;
            var currentSum = current.Value;

            // Calculate current sum
            currentSum = (currentSum * 10) + node.val;

            // We have reached a leaf node
            if (node.left == null && node.right == null) {
                result += currentSum;
            } else {
                // Keep traversing left and right calculating the sum
                if (node.left != null) {
                    stack.Push(new KeyValuePair<TreeNode, int>(node.left, currentSum));
                }
                if (node.right != null) {
                    stack.Push(new KeyValuePair<TreeNode, int>(node.right, currentSum));
                }
            }
        }
        return result;
    }
}// 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
58
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 3, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get sum root to leaf numbers
// ============================================================================
/**
 * 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 SumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // Declare stack
        var stack = new Stack<KeyValuePair<TreeNode, int>>();
        var result = 0;
 
        // Add root to stack
        stack.Push(new KeyValuePair<TreeNode, int>(root, 0));
 
        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node and running sum
            var current = stack.Pop();
            var node = current.Key;
            var currentSum = current.Value;
 
            // Calculate current sum
            currentSum = (currentSum * 10) + node.val;
 
            // We have reached a leaf node
            if (node.left == null && node.right == null) {
                result += currentSum;
            } else {
                // Keep traversing left and right calculating the sum
                if (node.left != null) {
                    stack.Push(new KeyValuePair<TreeNode, int>(node.left, currentSum));
                }
                if (node.right != null) {
                    stack.Push(new KeyValuePair<TreeNode, int>(node.right, currentSum));
                }
            }
        }
        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:

25 1026

Daily Archives: November 3, 2021

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

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

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories