Key Concepts

Review core concepts you need to learn to master this subject

Trees are composed of nodes

Tree nodes children

Nodes as parents

Wide and deep trees

Binary search tree

Python TreeNode class

Trees are composed of nodes

Trees are a data structure composed of nodes used for storing hierarchical data.

Each tree node typically stores a value and references to its child nodes.

Tree nodes children

A tree node contains a value, and can also include references to one or more additional tree nodes which are known as “children”.

Nodes as parents

Trees in computer science are often talked about similarly to family trees. A tree node that references one or more other nodes is called a “parent”.

A tree node can be a “parent” and a “child” simultaneously, because they are not exclusive. For instance, a node ‘b’ can be the child of node ‘a’, while being the parent to nodes ‘d’ and ‘e’. However, a child can only have one parent, while a parent can have multiple children.

Wide and deep trees

There are two ways to describe the shape of a tree. Trees can be wide, meaning that each node has many children. And trees can be deep, meaning that there are many parent-child connections with few siblings per node. Trees can be both wide and deep at the same time.

Binary search tree

In a binary search tree, parent nodes can have a maximum of two children. These children are called the “left child” and the “right child”. A binary search tree requires that the values stored by the left child are less than the value of the parent, and the values stored by the right child are greater than that of the parent.

Python TreeNode class

A TreeNode is a data structure that represents one entry of a tree, which is composed of multiple of such nodes.

The topmost node of a tree is called the “root”, and each node (with the exception of the root node) is associated with one parent node. Likewise, each node can have an arbitrary number of child nodes. An implementation of a TreeNode class in Python should have functions to add nodes, remove nodes, and traverse nodes within the tree.

Arrow Chevron Left Icon
Trees: Conceptual
Lesson 1 of 2
Arrow Chevron Right Icon
  1. 1
    Trees are an essential data structure for storing hierarchical data with a directed flow. Similar to linked lists and graphs, trees are composed of nodes which hold data. The diagram represents …
  2. 2
    Trees grow downwards in computer science, and a root node is at the very top. The root of this tree is /photos. /photos references to two other nodes: /safari and /wedding. /safari and /wedding …
  3. 3
    Trees come in various shapes and sizes depending on the dataset modeled. Some are wide, with parent nodes referencing many child nodes. Some are deep, with many parent-child relationships. Tre…
  4. 4
    Constraints are placed on the data or node arrangement of a tree to solve difficult problems like efficient search. A binary tree is a type of tree where each parent can have **no more than tw…
  5. 5
    Trees are useful for modeling data that has a hierarchical relationship which moves in the direction from parent to child. No child node will have more than one parent. To recap some terms: * ro…
  1. 1
    Before we start building (planting?) our trees, let’s do a quick inventory of what we’ll need in our Python implementation. We’re going to make the class TreeNodes. TreeNodes: - have a value - hav…
  2. 2
    Let’s start by defining our TreeNode class. We’ll begin with having our node store a value, and additional functionality can be layered on in the following exercises.
  3. 3
    We have a working TreeNode class, but there’s no time to enjoy a refreshing glass of lemonade. Trees are all about data hierarchy, and we need a parent-child relationship to make that work. To rev…
  4. 4
    Let’s explore how to remove nodes from a tree. Remember, child nodes are held in a list within the parent node. To remove a child, we need to remove that node from the list. We want the following …
  5. 5
    Trees are an abstract idea that we’re making concrete in Python. When implementing these abstract data structures, it’s important to leverage the features of your language. Let’s refactor .remove…
  6. 6
    Our implementation has covered adding and removing nodes. Let’s expand the functionality and add the ability to move through connected nodes. Tree traversal is a standard operation for finding no…
  7. 7
    Our implementation of tree traversal has a slight hiccup. Trees grow many levels deep, but we’ve only accounted for one parent-child relationship. How is this a problem? root = TreeNode(‘Founder’…
  8. 8
    Congratulations, you have implemented a tree in Python. For review, in our implementation: - Trees are a Python class called TreeNode. - A TreeNode has two properties, value and children. - Nodes …

What you'll create

Portfolio projects that showcase your new skills

Pro Logo

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo