← Home

TABLE OF CONTENTS

Univalued Binary Tree

February 02, 2020

yuck yuck

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

  1. Visit the root node - aka call helper on the root node
  2. Traverse the left subtree - aka, the internal helper call on node.left
  3. 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.

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.
Kevin Wang

👋 I'm Kevin Wang
🎓 New School for Jazz '13
💻 Software Engineer
🧗🏻‍♂️ Rock Climber

Comments

Create Post

You must log in to comment.

Be the first to comment!