Avi Mehenwal

# Trees

treedatastructurefundamental
  • Trees data structure can represent some form of hierarchy
  • A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more sub-trees.
  • Tree is a acyclic connected graph
    • If not connected, could be a forest

Tree Definition

For every tree , Maximum number of edges = number of vertices minus 1

proof by Induction

where,

Isomorphic Trees
Greek "same shape", 2 trees with same number of nodes, edges might have different connections
Vertices
set of all Nodes for a given tree T
Edges
ordered-pair of set of connecting nodes in the associative Array format (generally). Eg: {(a,b), (b,c), (a,c)}

A Isomorphic Tree examples

Graphs

All Trees are graphs, but all graphs are not tree.

why? because trees are Acyclic, meaning cannot have cycles

Cayley's formula
Calculate how many trees could be formed from given number of nodes

# Memory Representation of Tree

  1. Linear using Array
  2. Linked Lists using pointers

# Linear using Array

Element formula
Root Node
Left Child
Right Child
Parent

Example: To Do

text

Always analyze your solution, space time complexity

  • Function to implement unival trees?
  • How to implement auto-completion?
  • K-th largest number
    • Brute force technique
    • Improve your solution

# Operations on trees

# Traversal

  • BFS Breadth first Search
  • DFS Depth First Search

# Applications

←