Understanding Binary Trees | Tree Data Structure | Exploring Terminologies, Traversals, and Binary Search Trees | LeetCode Q | Resources

Introduction

What are trees? So, from the first click in our mind, after we listen the word 'trees' would be the picture which I have added on top. Trees in DSA also looks the same. So, previously we discussed about linear data structures (Linear data structurs are those, where we have stored elements in linear/single level or we can say that Data Structures where we store elements in sequential order, like one after the other and an element is connected to its next as well as previous elements, like Stack, LinkedLists, Priority Queues, Queue. All these are linear/sequential order. All these structures have single level. )

But trees on the other side are non-linear data structures, also we can say that trees are called as hierarchical data structures. What this means ? Let's discuss it with an example from our Government System. Pakistan's Government System has a prime minister ( the actual leader, who has power). Then, a prime minister declare his 32-33 ministers for different Ministries like for WAPDA, FBR, IT etc. Then, each minister has his/her Secretaries like Joint, Federal, Deputy Secretary. So, this is called as hierarchy, where things are ranked according to relative status or authority and there's some levels.

Another example, we can take of Family hierarchy, where let's suppose we have a person Ahmad, ahmad has three sons and two daughters. One of his sons name is Furqan, now Furqan is married and he has four daughters. One of his daughter has three sons.

So, this would make a hierarchy, where on the top we would have grand grand parents, then grand parents, then parents, then childs, then grand childs. And here you can see humans are ranked as relative status and authority. Like after parents, childs should come, not the grand childs.

I think you now perfectly understood what's the tree actually is. See the below pinned picture.

Tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.

Terminologies

While working on trees, we would be dealing with different terminologies. W'll discuss the most using words here.

• Node, these are the indiviual elements in tree. If we concern with family tree then eac human in the tree would be called as Node. And if we have a tree of integers, then each integer value would be a node.
• Edge, the connection between two nodes is called an edge. So, basically an edge connects parents to childs, and then childs to their childs and so on.
• Root, the whole tree starts from songle node, which always looks on the top of the tree. That top node is called as root. For example, King George IV ( See in the above picture where tree starts from King George IV).
• Leaf Node, those nodes which does'nt have any childs are called as leaf nodes.
• External Node, leaf nodes are also called as external nodes.
• Internal Node, except the leaf nodes all the nodes are called as external nodes. So, any nodes which has at least single child is an external node.
• Parent, the upper level node of any node is the parent of that node.
• Child, the very next lower level nodes af any node are childs for that node, that are directly connected. ( Note : See 'Directly Connected', means there should be an edge between them).
• Ancestor, any predecessor nodes that are directly or indirectly connected on the same path towards the roots are ancestors. (Note : 'Indirectly').
• Descendent, any successor nodes connected on the same path towards the leaf nodes is are descendent for that node. So, if King George IV is ancestor of Queen Elizbeth, it's means Queen Elizebth is descendent of King George IV. (See Figure).
• Sibling, two or more nodes having same parents are called as siblings. Also they don't share direct connection, but they indirectly connected through their parents.
• Level, each rank is classified as level. Like parents are on different level, parents'child are on next level and parent's grand childs are on the next to next level. Root has level 0. ( So Level start from 0..*. Just like indexing in array )
• Neighbour of a Node Parent or child nodes of that node are called neighbors of that node.
• Subtree Any node of the tree along with its descendants.

Two more important concepts :

• Depth, the number of edges from root node to that node in a tree is called as depth of tree. The depth of the root node is always 0 since there are no edges from the root to itself.
• Height, The height of a node in a tree is the number of edges on the longest path from that node to a leaf.

Types of Trees in DSA

There are many types of trees, we will be discussing some of them :

• Binary Trees, in such type of trees, each node can have at most 2 childs. So, if any tree has maximum of two childs then such a tree is binary tree. One is called as left child and other called as right.
• Strict/Perfect Binary Tree, if every non-leaf nodes in a binary tree has non empty elft and right child nodes, then the tree is called as Strict Binary Tree. So, in other words all the nodes has 0 or 2 child nodes. So, in a strict binary tree, each node has a degree 0 or 2, not 1. And in such type of trees, if we have N nodes then total number of nodes would be 2N - 1. Here, all leaf nodes will be on the same level (Last Level).
• Complete Binary Tree, the binary tree, in which all the levels are completely filled except the last one. Also in this binary tree nodes start insertin from left to right. So, here every node will first complete left subtree and start completing right subtree. So, in a nutshell odes in the last level are filled from left to right with no gaps in between.

• Binary Search Tree, trees in which left child has value less than parent's value and right's child has value greater than parent's value is called as BST and the same should be true for each subtree. One more thing, if we do preorder traversal of BST, the resulting array/list would be a sroted array.
• Degenerate/Pathological Tree, a tree where every internal node has exactly one child wether left or right is called as Pathological tree. Such tree just act same as linked lists in performance scenerio.

• Skewed Binary Tree, a skewed binary tree is a pathological tree in which the tree is dominated wether with the left nodes or right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.

• AVL Tree, An AVL tree defined as a self-balancing BST where the difference between heights of left and right subtrees for any node cannot be more than one.

Tree order Traversal

Traversing is the technique to visit all the nodes of the tree only once. Unlike the linear data structures where there's the only one logical way to traverse, trees can be traversed in different ways. We'll discuss all of them breifly here.Traversal is the most important thing in non-linear data structures. In most tree problems, traversal is the only thing needs to have understanding.

In Binary trees, we have two types of traversals:

• Depth First Search ( DFS )
• Breadth First Search ( BFS )

W'll discuss both types of traversals in next section.

Depth First Search -DFS

DFS is the technique, where we start traversing from the root and ends at the most right child. In this type of traversing, we traverse node by node. Like first parent then it's left then right, not all nodes in one step.

DFS has three traversal techniques :

• Preorder Traversal, from the word 'pre', we can understand that the parent would come before it's left and right child. So, the roo would come first, then left child and right child would come at the last. So the pattern is Root -> Left -> Right. Important: Preorder traversal is also used to get prefix expressions on an expression tree.
• Inorder Traversal, from the word 'In', we can understand that the parent would 'In' between the left and right child. First left child comes then root/parent comes and at the last right child comes. So, the pattern is Left -> Root -> Right. Important: The Inorder Traversal of Binary Search tree would give us sorted list in ascending order.
• Postorder Traversal, from the word 'post', we can come to the point that root would come at the post ( means at the last ). So, first we will traverse left child then right child and at the last root/parent. So, the pattern is Left -> Right -> Root. Important, Postorder traversal is used to delete the tree also this traversal is useful to get the postfix expression of an expression tree.

Breadth First Search -BFS

BFS is a level order traversal. Where we traverse all the nodes level by level not node by node. Like in the above picture of tree, we can see four levels for tree. So, in first turn we will visit root node. In second turn, two nodes will be visited because both are on same level. In 3rd turn, all the nodes on third level would be visited and so on.

For the BFS-Traversal we use queue ( deque ).

Some Properties of Binary Trees

• The maximum number of nodes at level 'L' in a binary tree is 2^L.
• If binary tree is a strict binary tree, then total number of nodes will be 2^L - 1, where L is the number of levels.
• The total number of nodes on any level in strict binary tree will be 2^h, where h will be the height of tree.
• The Maximum number of nodes in a binary tree of height ‘h’ is 2^h – 1.
• In a Binary tree where every node has 0 or 2 children (Strict/Perfect Binary Tree), the number of leaf nodes is always one more than nodes with two children, like if nodes with 2 childern are 1, then leaf nodes would be 1 + 1 = 2. So, relation is Leaf = TwoNodes + 1.

LeetCode Question as an Example

• Problem Title : Closest Nodes Queries in a Binary Search Tree.
• Difficulty : Medium

Statement : You are given the root of a binary search tree and an array queries of size n consisting of positive integers.

Find a 2D array answer of size n where answer[i] = [mini, maxi]:

• mini is the largest value in the tree that is smaller than or equal to queries[i]. If a such value does not exist, add -1 instead.
• maxi is the smallest value in the tree that is greater than or equal to queries[i]. If a such value does not exist, add -1 instead.

Return the array answer.

Coding Solution in Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
       
        def DFS(node, data):
            if not node:
                return None

            DFS(node.left, data)
            data.append(node.val)
            DFS(node.right, data)
        
        data = []
        DFS(root, data)
        n = len(data)

        def calc(val):
            index = bisect.bisect_left(data, val)
            if index == n:
                return data[-1], -1
            if data[index] == val:
                return [val, val]
            if index == 0:
                return [-1, data[0]]
            
            return [data[index-1], data[index]]

        
        return [calc(val) for val in queries]        

Explanation of Solution

Consider the above example, where the querues list is [2, 5, 16]. So, first of all in the above code, we can see that we have defined a node class. This class is commented by LeetCode, which says us not to change the code of node class, becuase our code will be judged based on thier provided Node class, not ours.

In the Node Class, we have the current Node's value, it's left child's address and also it's right child's address.

In the Solution Class, when the excecution of our defined function starts, the line which will first excecute would be the line number : 18 where we are defining our list, because before this we only defined our function.

On line number 19, we called our function DFS(), and if we look on our function, we can clearly see that the function is an InOrder Traversal, and here instead of just printing we are storing the nodes as we traverse throughout the tree. Also, we kow that the Inorder traversal of BST(Binary Search Tree) give us sorted list. So, the array:data[] would have the sorted node's values in sorted way.

So, after the excution of line number of 19, and our function DFS() completely terminated then array : data = [ 1, 2, 4, 6, 9, 13, 14, 15 ].

Now, we again defined a function named calc(), let's see what er are calculating and how. So, in the first line of function, we are using bisect.bisect_left(x, y) function. biect.bisect_left() function always apply on sorted list x, and returns the index like where we can insert 'y' in 'x'. So that the list 'x' remains sorted as it was before. As it's bisect_left function, so it preferred first to insert element at the left side, if inserting on left side makes array unsorted then it inserted it on right side. Let's take an exampe, suppose we have array named L[1, 4, 6], and we want to insrt '3' in L with the condition that 'L' remains sorted, so we call function bisect.bisect_left ( L, 3 ). Here, our function will return index = 1, because the list would remain sorted if '3' will be on index 1. Also, we can have a poin here, that it was sure that '3' would always be on the left of '4' in sorted array, then why we are using here specifically biesct.bisect_left function ? Let's understand this by letting another case, suppose we want to insert '4' in L[ 1, 4, 6]. Now, if we call bisect.bisect_left( L, 4 ) then this function will return again '1', because it will see that if '4' inserts on index no. 2 or on index number 1 our list will remin sorted in both cases, but as in this case, it was bisect_left function that's why it will return use left index to insert, that would be '1'. But function bisect_right() will return '2' index in this case.

So, in the last line we are running a for loop where we are passing queries[ 2, 5, 15 ] elements one by one to calc function. When we pass queries[0] (2) element to calc(), bisect_left () will give us index no. '1', as in data = [ 1, 2, 4, 6, 9, 13, 14, 15 ], '2' can be inserted on index 1. Now check the if conditions, we can see that the second if condition meets with this scenerio where data[1] = queires[0] ( val which we passed, and '1' is the returned index from bisect function), So we will return a list [ 2, 2 ].

The same will happen for other tqo queries, and as the for loop ends, this would directly return as an answer.

Resources

• Solution Link on Python Complier, here you can view and check the solution on compiler, of above problem discussed.
• Solution Link Github Repository, here you can find out three solutions with different approaches which I mentioned in my GitHub repository.
• LeetCode Questions Solutions on Trees, in this GitHub Repository you can find out more than 20 LeetCode questions on Binary Trees alongwith their solutions in python.
• 300 LeetCode Question/Solutions Repository, here in this Repository I uploaded 300+ LeetCode question's Solutions in Python.
• GitHub Repository for Recursion, View Problems Solved with Recursion and their Solutions also with Arrays in this repository.
• DSA in CpluPlus View the GitHub Repository to check and to analyze how to complete DSA in C++.
• Article on Recursion, for better understanding and best command on trees problems, do your best for recursion, for this you can look at my Article on Recursion.

#BinaryTree #TreeDataStructure #DataStructures #Algorithms #BinaryTreeTraversal #BinarySearchTree #TreeNodes #Coding #Programming #TechEducation #ComputerScience #TreeTraversal #DFS #BFS #LearnCoding #BinaryTreeBasics #TreesInPython #DataStructureAndAlgorithm #CodeLearning #ProgrammingTips

美国亚利桑那州立大学 Python Coding Python programming MATLAB & PYTHON DSA iCodeGuru University of Engineering and Technology, Lahore