Trees

By: Johnny Lu

Sign in here!

https://linktr.ee/bingacm

What are trees?

• Nonlinear data structure

​

• Collection of nodes connected by edges

​

• Data stored in nodes

Some Types of Trees

01

02

03

AVL Trees

Huffman Tree

Red-Black Trees

Binary Tree

• Each node has at most 2 children

​

​

Terminology

​

• Root, Node, Edge, Leaf
• Parent, Child

​

Root

Leaf

Edge

Root of this left subtree = 2

Root of this right subtree = 3

Binary Search Tree

Tree Traversals

How do we access the values stored in trees?

Algorithms that let us visit all the nodes in a tree

2

1

3

Recursion

A function that calls itself (recursive function)

#recursive function that finds the sum of first n natural numbers

def recursiveSum(n):

if n <= 0:

return n

return n + recursiveSum(n-1)

​

​

Example:

n=3 has output of 6

Depth First Search (DFS)

Typically done recursively

• Preorder Traversal - (Root, Left, Right) -> (1, 2, 5, 6, 3)
• Inorder Traversal - (Left, Root, Right) -> (5, 2, 6, 1, 3)
• Postorder Traversal - (Left, Right, Root) -> (2, 5, 6, 3, 1)

Visits lowest depth of tree first

Breadth First Search (BFS)

Typically done using a queue as opposed to recursion

Visits all of a node’s children before visiting their children

[[1], [2, 3], [5, 6]]

Tree Methods

​

​

​

​

Given the root of a binary tree, return the preorder traversal of its nodes' values.

​

144 - Binary Tree Preorder Traversal

Python

Java

Inorder

Preorder

Postorder

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

​

104 - Maximum Depth of Binary Tree

Python

Java

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

​

102 - Binary Tree Level Order Traversal

Python

Thank you for coming!