Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a binary tree root, return whether for every node in the tree other than the leaves, its value is equal to the sum of its left child’s value and its right child’s value.
Constraints
n ≤ 100,000 where n is the number of nodes in root
Determine Sum Binary Tree via Breadth First Search Algorithm
We can traverse the binary tree using level by level aka Breadth First Search algorithm. And we check if the node’s value equal to the sum of its children (if any).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSumBinaryTree(self, root): if not root: return True q = deque([root]) while q: cur = q.popleft() s = 0 if cur.left: q.append(cur.left) s += cur.left.val if cur.right: q.append(cur.right) s += cur.right.val if cur.left or cur.right: if s != cur.val: return False return True |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSumBinaryTree(self, root):
if not root:
return True
q = deque([root])
while q:
cur = q.popleft()
s = 0
if cur.left:
q.append(cur.left)
s += cur.left.val
if cur.right:
q.append(cur.right)
s += cur.right.val
if cur.left or cur.right:
if s != cur.val:
return False
return TrueWe need the queue to implement the BFS. The time complexity is O(N) and space complexity is also O(N) where N is the number of the nodes for the given binary tree.
Hey, we can also traverse the binary tree using Recursive Depth First Search Algorithm: Teaching Kids Programming – Depth First Search Algorithm to Determine Sum Binary Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Javascript/NodeJS Function to Check the Plugins on Steem Blockchain RPC Nodes
Next Post: A Bash Process Controller to Start, Stop and Restart an Daemon Program