How to Improve the Runtime of Your Code When Checking the Value of a Binary Tree’s Root

The original problem of “2236. Root Equals Sum of Children” was published on LeetCode.com

You are given the root of a binary tree that consists of exactly 3 nodes: the root, its left child, and its right child.

Return true if the value of the root is equal to the sum of the values of its two children, or false otherwise.

Example 1:

Input: root = [10,4,6]
Output: true
Explanation: The values of the root, its left child, and its right child are 10, 4, and 6, respectively.
10 is equal to 4 + 6, so we return true.

Example 2:

Input: root = [5,3,1]
Output: false
Explanation: The values of the root, its left child, and its right child are 5, 3, and 1, respectively.
5 is not equal to 3 + 1, so we return false.

Constraints:

• The tree consists only of the root, its left child, and its right child.
• -100 <= Node.val <= 100

Solution

To solve this problem, you need to understand the basics of binary trees and the concept of tree traversals. You will also need to know how to access the values of each node in the tree, as well as the logic behind checking if the value of the root is equal to the sum of its child nodes. Once you have this knowledge, you can work on developing a solution that will iterate through the tree and check each node against the condition provided.

What are the basics of binary trees and the concept of tree traversals?

A binary tree consists of nodes, each of which contains a value, as well as two child nodes that may or may not have their own child nodes. A tree traversal is a process that uses a set of steps to traverse through the tree’s nodes. The three main types of tree traversals are pre-order, in-order, and post-order. Pre-order traversal visits a node before any of its children, in-order traversal visits a node between its children, and post-order traversal visits a node after all of its children.

How to access the values of each node in the tree

To access the values of each node in the tree, you can use the tree traversal method to traverse through the nodes and retrieve the values. For example, if you are using the pre-order technique, you would start at the root of the tree and retrieve the value of the root before traversing to its children. Once you have retrieved the values of the root’s children, you can then traverse to their children, and so on, until all the values are retrieved.

What is the logic behind checking if the value of the root is equal to the sum of its child nodes?

The logic behind checking if the value of the root is equal to the sum of its child nodes is to traverse through the tree and add the values of the root’s children together. If the value of the root is equal to the sum of its child nodes, then the condition is true, and the function should return true. Otherwise, the function should return false.

Let’s develop a solution in Python with an explanation.

The following is a solution to the problem written in Python. First, we define a function called checkTree that takes in a single node (the root of the tree) as an argument. Inside this function, we create a variable called sum and initialize it to 0. We then traverse through the tree using the pre-order traversal technique, adding the values of the nodes to the sum variable. Once all the values have been traversed, we check if the value of the root equals the sum of its child nodes. If it is, we return true; otherwise, we return false.

def checkTree(self, root): 
        # Initialize sum 
        sum = 0
  
        # Traverse through tree and add each node's value to sum 
        if root.left is not None:
            sum += root.left.val 
        if root.right is not None:
            sum += root.right.val
  
        # Check if the value of the root is equal to the sum of its child nodes
        if root.val == sum:
            return True
        else: 
            return False

Can the runtime of the above code be improved?

Yes, the runtime of the above code can be improved. For example, instead of traversing through the tree and adding the values of the nodes to the sum variable, we can use a single comparison to check if the value of the root is equal to the sum of its child nodes. This would reduce the code’s runtime from O(n) to O(1).

Let’s do that with an explanation.

The following solution improves the code’s runtime from O(n) to O(1). First, we define a function called checkTree that takes in a single node (the root of the tree) as an argument. Inside this function, we create two variables called leftVal and rightVal and initialize them to 0. We then check if the root’s left and right children are not None, and if they are not, we assign their values to the leftVal and rightVal variables, respectively. Finally, we check if the value of the root is equal to the sum of its child nodes. If it is, we return true; otherwise, we return false.

def checkTree(self, root): 
        # Initialize leftVal and rightVal 
        leftVal = 0
        rightVal = 0
  
        # Check if the root's left and right children are not None 
        if root.left is not None:
            leftVal = root.left.val 
        if root.right is not None:
            rightVal = root.right.val
  
        # Check if the value of the root is equal to the sum of its child nodes
        if root.val == leftVal + rightVal:
            return True
        else: 
            return False

The runtime of each code and the improvements made.

The original code had a runtime of O(n) as it traversed through the tree and added the values of the nodes to the sum variable. The improved code had a runtime of O(1), as it used a single comparison to check if the value of the root is equal to the sum of its child nodes. This improved the runtime of the code by eliminating the need to traverse through the tree and add the values of the nodes to the sum variable.

Check out my submission on leetcode.com:
https://leetcode.com/problems/root-equals-sum-of-children/submissions/885636934/