Category Archives: Binary Tree

Handshaking Lemma and Trees

Handshaking Lemma and Trees What is Handshaking Lemma? Degree of a vertex is number of edges incident on it. Handshaking Lemma states that, in every finite undirected graph, number of vertices with odd degree is always even. The handshaking lemma is a consequence of the degree sum formula: The vertices of odd degree in a… Read More »

Binary Tree and its Properties

Binary Tree and its Properties Following are some properties of binary trees. The maximum number of nodes at a given level, k of a binary tree is 2k-1. Level of root is taken to be 1 above. This can be proved by induction. For root, k = 1 Therefore, number of nodes = 2k-1 = 1… Read More »

Types of Binary Tree

Types of Binary Tree Given below are different types of Binary tree : Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. Following are examples of full binary tree. In a Full Binary, number of leaf nodes is number of internal nodes plus 1 Mathematically, L = I… Read More »

Binary Tree Introduction

Introduction to Binary Tree Trees are hierarchical data structures. The topmost node is called root of the tree. The elements that are directly under an element are called its children. The element directly above something is called its parent. Elements with no children are called leaf nodes or leaves. A tree whose elements have at most 2… Read More »

Check if a Binary Tree is BST or not

Check if a Binary Tree is BST or not Given a Binary Tree, we need to print the level of a given data/node in the Binary Tree, or print a statement to tell it is absent from the tree in case it is not present. Check if a Binary Tree is BST or not Example:… Read More »

Level of a Given Node

Finding Level of a Given Node in a Binary Tree. Given a Binary Tree, we need to print the level of a given data/node in the Binary Tree, or print a statement to tell it is absent from the tree in case it is not present. Level of a Given Node in a Binary Tree… Read More »

Left and Right View of a Binary Tree

Left View of a Binary Tree. Right View of a Binary Tree. Given a binary tree, we need to print how the tree will look when viewed from left side and right side. Left and Right View of a Binary Tree Example: 80 / \ 60 110 / \ / 35 40 85 / \ 64… Read More »

Count Leaf Nodes in a Binary Tree

Counting Leaf Nodes in a Binary Tree. Count Leaf Nodes in a Binary Tree problem Statement: Given a Binary Tree, we need to output the number of leaf nodes in it. A leaf node is one, which had both its left and right child NULL. Counting Leaf Nodes in a Binary Tree example: Given this… Read More »

Delete a Binary Tree

Program to Delete a Binary Tree. Delete a Binary Tree Problem Statement: Given a binary tree, we need to delete the complete tree. The root pointer should have a value NULL after the completion of the operation. This is sometimes called as destructor for binary tree. Delete a Binary Tree Example: The input tree : 80… Read More »

Height of a Binary Tree

Height of a Binary Tree Given a Binary Tree, we need to print the height of the tree (or the maximum depth). Example: 80 / \ 60 110 / \ / 35 40 85 / \ 64 72 For the tree shown above, the output should be 4. height of tree = max { height… Read More »