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!)”*

## 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

**is the total number of nodes.**

`n`

### 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

**is the greatest depth of a subtree. (This needs confirmation. Someone save me.)**

`h`

## 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.

👋 I'm Kevin Wang. ~~Jazz Guitarist~~ → ~~Barista~~ → ~~Receptionist~~ → __Front End Engineer__

This is my ever growing sandbox of sorts⛱.

### Comments

You must log in to comment.

Be the first to comment!