In this post I will walk you through a process of finding the maximum diameter of a given binary tree.
The implementation of the code is in C++, however, it could be achieved in any other language, therefore, we’ll discuss the idea first, after few definitions of key terms along the post. Enjoy!
Terms to be used:
- Binary Tree: it is simply a tree, whereas each node has 0,1 or 2 sons. Simple as that!
- Diameter:
A path that connects 2 leaves in the tree. Thus, if the tree consists of 1 nodes(i.e only root), then the diameter is zero. However, that path does not necessarily go through the root of the tree, for example: in the above binary tree, a diameter could be any of the following:
diameter1: G->E->C->F->I which equals to 5
diameter2: I->F->H which equals to 3
diameter3: D->B->A->C->F->I which equals to 6
...
Therefore, we can have the max diameter from a path that doesn’t pass through the root(in this example it’s D
)
3. Max depth: It is the path from the root to any of the leaves which consists of the largest amount of nodes.
4. Root: It is a node in the tree, whereas there is only one certain unique path from the root to each leaf in the tree
Attacking the problem
Let’s start by remembering the problem again:
We need to find the largest diameter in a given tree.
Starting from the root, if we had zero sons, then the diameter is 1. However, if we had 1 son, then we could find the depth of the tree from that son and this would be our diameter. Lastly if we have 2 sons, then we find the depth of the tree from the left son, add to it the depth of the tree from the right son, and thus we have a diameter!
Since the diameter doesn’t necessary pass through the root, then each time we calculate a new diameter, we must compare it with the old diameter, if the new one is bigger, then our max would be it.
Until now, we can see how tempting it is to use recursion in order to scan all the options of pather and diameters per pair of possible nodes!
Implantation in C++
I broke the program into 2 files:
- Header file with
BinaryTree
class Driver
source file(.cpp) with themain()
function, so we can test the program and see it running.
Testing the program with 2 general tests that imply most of the critical cases as well as the normal ones.
For the sake of simplicity, I made a whole struct
that holds everything included in a Node
which are: leftSone, rightSone, data
. Moreover, in the class BinaryTree
itself, I made use of 2 recursive functions declared as methods(private) that are being called by 2 public methods, thus they(methods) serve as private auxiliary functions.
Without further ado, let’s see the code and the screen shot of the output at the end:
Code: BinaryTree() – Class
/* * binaryTree.h * Created on: 24 February 2015 * Author: bassam */ #ifndef BINARYTREE_H_ #define BINARYTREE_H_ /**********************************************************************/ /* * SUMMARY: * In this header there is the class 'BinaryTree'- * with all its methods and functions implemented */ /**********************************************************************/ /*_includes_*/ #include <vector> #include <stdio.h> /**********************************************************************/ /*_DEFINES_*/ const int EMPTY = 0; const int NO_DIAMETER = 0; const int SINGLR_NODE_TREE = 1; const int CURRENT_NODE = 1; const int COMMON_NODE = 1; const int START = 1; /**********************************************************************/ /* * struct of the basic unit in the binary tree */ struct Node { Node *leftSon, *rightSon; int data; Node(int data = EMPTY) : leftSon(NULL), rightSon(NULL), data(data) {} }; /**********************************************************************/ /* * - A class that contains all the nodes of a tree. * - Provides basic tools to edit the tree * - calculates the max diameter of the tree */ class BinaryTree { private: Node root; /*methods:*/ int hight_aux(const Node* head) const; int diameter_aux(const Node* head, const int oldMax) const; public: /*constructor:*/ BinaryTree(Node root = Node()) : root(root) {} /*functions:*/ int hight() const; int maxDiameter() const; }; /*end of BinaryTree{}*/ /**********************************************************************/ /*implementation of class methods*/ /**********************************************************************/ int BinaryTree::hight_aux(const Node* head) const { int hightLeft(EMPTY), hightRight(EMPTY); if(head == NULL) { return EMPTY; } else if((head->leftSon == NULL) && (head->rightSon == NULL)) { return SINGLR_NODE_TREE; } else { hightLeft = CURRENT_NODE + hight_aux(head->leftSon); hightRight = CURRENT_NODE + hight_aux(head->rightSon); } return (hightLeft >= hightRight) ? hightLeft : hightRight; } /**********************************************************************/ /* * Calculates the diameter of a tree, and return the max diameter in * Comparison to the 'oldMax' */ int BinaryTree::diameter_aux(const Node* head, const int oldDiameter) const { if((head == NULL) || (!head->leftSon && !head->rightSon)) { return oldDiameter; } int thisDiameter(EMPTY); thisDiameter = (hight_aux(head->leftSon) + hight_aux(head->rightSon) + COMMON_NODE); thisDiameter = (thisDiameter > oldDiameter) ? thisDiameter : oldDiameter; int diam1(EMPTY), diam2(EMPTY); diam1 = diameter_aux(head->leftSon, thisDiameter); diam2 = diameter_aux(head->rightSon, thisDiameter); return (diam1 > diam2) ? diam1 : diam2; } /**********************************************************************/ /*implementation of class functions*/ /**********************************************************************/ /* * returns the (max)depth of a binary tree which root is passed- * to the function as an argument. * However, the calculation is done by an- auxiliary method. */ int BinaryTree::hight() const { return hight_aux(&root); } /*end of depth()*/ /**********************************************************************/ /* * return the max diameter of a binary tree which head is passed- * to the function as an argument */ int BinaryTree::maxDiameter() const { return diameter_aux(&root, EMPTY); } #endif /* BINARYTREE_H_ */
Code: Driver Main() function
/* * driver.cpp * * Created on: 24 February 2015 * Author: bassam */ /* * SUMMARY: * main source file that runs and tests 'binaryTree.h' * */ /**********************************************************************/ /*_includes_*/ #include <vector> #include <stdio.h> #include <iostream> #include "binaryTree.h" /**********************************************************************/ using namespace std; /**********************************************************************/ int main() { /*test1:*/ Node root = Node(); Node leaf1 = Node(); Node leaf2 = Node(); Node leaf3 = Node(); /* * Building the following tree: * (root) * / \ * (leaf1) (leaf2) * \ * (leaf3) */ root.leftSon = &leaf1; root.rightSon = &leaf2; root.rightSon->leftSon = &leaf3; BinaryTree tree1 = BinaryTree(root); cout << "max diameter of tree1 = " <<tree1.maxDiameter() << endl; /**********************************************************************/ /*test2:*/ /* * Building the following tree: * (n1) * \ * (n2) * / * (n3) * / \ * (n4) (n7) * / \ * (n5) (n8) * / / \ * (n6) (n11) (n9) * \ * (n10) */ Node n1 = Node(1); Node n2 = Node(2); Node n3 = Node(3); Node n4 = Node(4); Node n5 = Node(5); Node n6 = Node(6); Node n7 = Node(7); Node n8 = Node(8); Node n9 = Node(9); Node n10 = Node(10); Node n11 = Node(11); n1.rightSon = &n2; n2.leftSon = &n3; n3.rightSon = &n7; n3.leftSon = &n4; n4.leftSon = &n5; n5.leftSon = &n6; n7.rightSon = &n8; n8.rightSon = &n9; n8.leftSon = &n11; n9.rightSon = &n10; BinaryTree tree2 = BinaryTree(n1); BinaryTree tree3 = BinaryTree(n4); BinaryTree tree4 = BinaryTree(); BinaryTree tree5 = BinaryTree(n10); cout << "max diameter of tree2 = " <<tree2.maxDiameter() << endl; cout << "max diameter of tree3 = " <<tree3.maxDiameter() << endl; cout << "max diameter of tree4 = " <<tree4.maxDiameter() << endl; cout << "max diameter of tree5 = " <<tree5.maxDiameter() << endl; return 0; }
Output:
Hope that you liked this post, for any questions, please leave me a comment bellow!
kya h ye bc..
LikeLike
what does that mean?!
LikeLike