Univalued Binary Tree

Last night, in the mildewy smelling basemeent of some KBBQ restaurant near Flushing (NY), a few friends and I were talking about snowboarding, and how it took one of us 5 years to get comfortable with it. Why so long? “Well I only go once a year!”, was the response. And that makes total sense.

A quick pivot to this morning - I’m staring at a leetcode question, Univalued Binary Tree, scanning the past year for anything useful I’ve learned, and wondering why I still feel so dumbfounded, like a deer in headlights. My response to myself? “Well I only practice once every few months. (And I don’t even like it!)”

Reminders to myself…

What’s the movtivation behind practing coding questions?

You suck, try harder - Ok!

How do you expect to pass the next job interview? - Luck?

Is not knowing common algorithm patterns / problem solving stunting my growth as a “budding” software engineer? - Yes

Don’t be lazy

I’m not going to magically understand how to solve coding questions. I just have to do it more.

Ugh…

Use any helpful tools

Haters will probably hate, but I find Joma & TechLead’s coding website immensely useful, given the limited amount of free time that I have in a day. (Commuting, working, staying late after work, climbing, doing life chores…)

The question

Link: https://leetcode.com/problems/univalued-binary-tree/

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

My answer

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        def helper(node: TreeNode, unival) -> bool:
            if not node:
                return True
            if node.val != unival:
                return False
            if not helper(node.left, unival):
                return False
            if not helper(node.right, unival):
                return False
            return True

        if not root:
            return True
        return helper(root, root.val)

Approach

Recursion is an easy way to traverse a tree. I took this approach from Joma and TechLead’s answer to this other binary tree question, and modified it to take a unival param.

def helper(node: TreeNode, unival) -> bool:
# ...

Each recursive call will be given the unival for a node’s key/val to be checked against.

…But since unival will be a constant, starting from the root node, maybe this can be a global value rather passed down as “state” in each recursive helper call, right?…

TODO: read this stackoverflow thread for better fundamental understanding of how the “callstack” works.

Time Complexity

Visit the root node - aka call helper on the root node
Traverse the left subtree - aka, the internal helper call on node.left
Traverse the right subtree - aka, the internal helper call on node.right

Each node will be visited once, so: O(n), where n is the total number of nodes.

Space Complexity

This is something I still don’t fully understand.

TODO: read this stackoverflow thread to understand space complexity of recursive functions.

Space complexity depends on how fast the callstack grows. The callstack grows with each recursive call, and recursive calls stop when a “leaf node” or base-cases are reached.

Space complexity will be O(h), where h is the greatest depth of a subtree. (This needs confirmation. Someone save me.)

Next Steps

Take a break.
Learn some more RESTful api basics, as well as Express.
Take a break from Apollo + GraphQL, as amazing as they are.
Do some more database stuff - learn some SQL. I revived my RDS instance, so I should probably make use of that $20+/month that I’m paying.

← Home