A Binary Tree is a non-linear data structure that is used for searching and data organization. A binary tree is comprised of nodes. Each node being a data component, one a left child and the other the
A Binary Tree is a non-linear data structure that is used for searching and data organization. A binary tree is comprised of nodes. Each node being a data component, one a left child and the other the right child. Let us dive into the concepts related to trees and implement them into the Python programming language.
Note: Prerequisites – Make sure you have basic Python knowledge before diving into this article. It also might be a good idea to check out some linear data structures. (links are given above)
A binary tree node consists of the following components:
Data
Pointer to Left Child
Pointer to Right Child
Below are some key terminologies related to a binary tree.
Node – The most elementary unit of a binary tree.
Root – The root of a binary is the topmost element. There is only one root in a binary tree.
Leaf – The leaves of a binary tree are the nodes which have no children.
Level – The level is the generation of the respective node. The root has level 0, the children of the root node is at level 1, the grandchildren of the root node is at level 2 and so on.
Parent – The parent of a node is the node that is one level upward of the node.
Child – The children of a node are the nodes that are one level downward of the node.
A binary tree is a hierarchical data structure, a file system that is organized in the form of a tree. Trees can be used for efficient searching, when the elements are organized with some order. Some examples include:
The HTML/XML Document Object Model is organized in the form of a tree.
Abstract Syntax Trees and Parse Trees are constructed by a compiler as a part of compilation.
Trees are also used to efficiently index databases.
Initialize a Node Class
Let us first define the Node class.
Once we have defined the Node class, we can initialize our Binary Tree:
Since a binary tree is a non-linear data structure, there is more than one way to traverse through the tree data. Let’s look at the various types of traversals in a binary tree, including inorder traversal, preorder traversal, and postorder traversal.
Inorder Traversal
In an inorder traversal, the left child is visited first, followed by the parent node, then followed by the right child.
Preorder Traversal
In a preorder traversal, the root node is visited first, followed by the left child, then the right child.
Postorder Traversal
In a postorder traversal, the left child is visited first, followed by the right child, then the root node.
Once you have understood the core concepts of a binary tree, practice the problem sets given below to strengthen and test your knowledge on trees.
Flatten Binary Tree to Linked List - LeetCode
Sum Root to Leaf Numbers - LeetCode
Symmetric Tree - LeetCode
Binary Trees - Carnegie Mellon University
Explain and implement a Binary Tree.
A tree is a collection of nodes and edges between them.
It cannot have any cycles, which are edges that form a loop between nodes.
We also only consider rooted trees in computer science, which is a tree that has one root node that is able to access all other nodes.
For a tree to be a binary tree, each node can have a maximum of two children.
It's important to be able to identify and explain tree terminology as well. If given a tree, be able to point out each component.
root: The single node of a tree that can access every other node through edges.
parent node: A node that is connected to lower nodes in the tree. If a tree only has one node, it is not a parent node because there are no children.
child node: A node that is connected to a higher node in the tree. Every node except for the root is a child node of some parent.
sibling nodes: Nodes that have the same parent.
leaf node: A node that has no children (at the ends of the branches of the tree)
internal node: A non-leaf node (aka a parent)
path: A series of nodes that can be traveled through edges.
subtree: A smaller portion of the original tree. Any node that is not the root node is itself the root of a subtree.
Know the basics of each term
A non-empty tree has to have a root.
A tree doesn't have any parent nodes if there are no children.
What's the min/max number of parent and leaf nodes for a tree with 5 nodes?
Implementing as a balanced tree results in min number of parents and max number of leaves: 2 parents, 3 leaves
All that we need in order to implement a binary tree is a TreeNode class that can store a value and references to a left and right child. We can create a tree by assigning the left and right properties to point to other TreeNode instances:
Identify the three types of tree traversals: pre-order, in-order, and post-order.
Pre-order: Values are accessed as soon as the node is reached.
In-order: Values are accessed after we have fully explored the left but before we explore the right branch.
Post-order: Values are accessed after all of our children have been accessed.
*Breadth First: The previous three are types of Depth First Traversals. Breadth first accesses values of nodes by level, left to right, top to bottom.
Breadth First: 20, 9, 24, 7, 11, 23, 27, 3, 10, 17, 36, 30
Pre-order: 20, 9, 7, 3, 11, 10, 17, 24, 23, 27, 36, 30
In-order: 3, 7, 9, 10, 11, 17, 20, 23, 24, 27, 30, 36
Post-order: 3, 7, 10, 17, 11, 9, 23, 30, 36, 27, 24, 20
Explain and implement a Binary Search Tree.
A binary search tree is a binary tree with the added stipulation that all values to the left of a node are less than its value and all values to the right are greater than its value.
Example of a BST with an insert method. You won't be asked to implement a removal:
Given a binary tree class that looks like this:
write a function that checks to see if a given binary tree is perfectly balanced, meaning all leaf nodes are located at the same depth. Your function should return true
if the tree is perfectly balanced and false
otherwise.
Analyze the time and space complexity of your function.
JS Solution:
Given an array that is sorted in ascending order containing unique integer elements, write a function that receives the sorted array as input and creates a valid binary search tree with minimal height.
For example, given an array [1, 2, 3, 4, 5, 6, 7]
, your function should return a binary search tree with the form
Note that when we say "binary search tree" in this case, we're just talking about a tree that exhibits the expected form of a binary search tree. The tree in this case won't have an insert
method that does the work of receiving a value and then inserting it in a valid spot in the binary search tree. Your function should place the values in valid spots that adhere to the rules of binary search trees, while also seeking to minimize the overall height of the tree.
Here's a BinaryTreeNode
class that you can use to construct a binary search tree:
Analyze the time and space complexity of your solution.
This problem asks us to create a valid binary search tree from a sorted array of integers. More specifically, the resulting binary search tree needs to be of minimal height. Our function should return the root node of the created binary search tree.
From the given example where the input is [1, 2, 3, 4, 5, 6, 7]
, the expected answer is a binary search tree of height 3. This is the minimal height that can be achieved for an array of 7 seven elements. Try as we might, there's no way to construct a binary search tree containing all of these elements that has a shorter height.
A straightforward way to do this would be to take the first element of our array, call that the root, and then iterate through the rest of our array, adding those elements as nodes in the binary search tree. In pseudocode, that might look something like this:
Figure: Binary Trees, Image Source
Two extreme implementations:
Implementing in a chain results in max number of parents and min number of leaves: 4 parents, 1 leaf
Given a tree, be able to determine the order of each traversal type:
Recommended: Please solve it on "PRACTICE" first, before moving on to the solution.
A simple solution is to traverse the tree and do following for every traversed node X. 1) Find maximum sum from leaf to root in left subtree of X (we can use this post for this and next steps) 2) Find maximum sum from leaf to root in right subtree of X. 3) Add the above two calculated values and X->data and compare the sum with the maximum value obtained so far and update the maximum value. 4) Return the maximum value. The time complexity of above solution is O(n2) We can find the maximum sum using single traversal of binary tree. The idea is to maintain two values in recursive calls
(Note: If the tree is right-most or left-most tree then first we have to adjust the tree such that both the right and left are not null. Left-most means if the right of super root of the tree is null and right-most tree means if left of super root of the tree is null.)
1) Maximum root to leaf path sum for the subtree rooted under current node. 2) The maximum path sum between leaves (desired output). For every visited node X, we find the maximum root to leaf sum in left and right subtrees of X. We add the two values with X->data, and compare the sum with maximum path sum found so far.
Python
Output
Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another. The maximum sum path may or may not go through root. For example, in the following binary tree, the maximum sum is 27(3 + 6 + 9 + 0 - 1 + 10). Expected time complexity is O(n). If one side of root is empty, then function should return minus infinite (INT_MIN in case of C/C++)