TABLE OF CONTENTS
Univalued Binary Tree
February 02, 2020
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!)”
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
I’m not going to magically understand how to solve coding questions. I just have to do it more.
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…)
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.
# 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)
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
def helper(node: TreeNode, unival) -> bool: # ...
Each recursive call will be given the
unival for a node’s key/val to be checked against.
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.
- Visit the root node - aka call
helperon the root node
- Traverse the left subtree - aka, the internal
- Traverse the right subtree - aka, the internal
Each node will be visited once, so:
n is the total number of nodes.
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
h is the greatest depth of a subtree.
(This needs confirmation. Someone save me.)
- 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.
👋 I'm Kevin Wang.
Jazz Guitarist → Barista → Receptionist → Front End Engineer
This is my ever growing sandbox of sorts⛱.
You must log in to comment.
Be the first to comment!