Strahler Number of a Binary Tree

This post is going to cover how to find a strahler number of a binary tree. We are going to start by explaining what a strahler number is, the algorithm for finding a strahler number and I will also provide a nice little program to demonstrate this. I provide no source code for the program, but I will be more than happy to assist you with any problems you might encounter writing a program for a strahler number.

1. Strahler Number - Description and Algorithm

The Strahler Number is the branching complexity of a tree. It has been introduced by hydrologists for studying the morphology of the river networks and was later used in computer science regarding some optimization problems. The Strahler number can be defined by the following recursive rule:

Recursive rule for strahler number

The notation that we use is strahler(L, r, R) - L refers to the left subtree, r is the root, and R is the right subtree. The way the algorithm works is that all leaf nodes are assigned a strahler number of 1. If a node has only one child, it is assigned the strahler number of its child. This is also defined by the recursion above which checks whether strahler(L) == strahler(R). When a parent has only one child, then we take the max of strahler(L) and strahler(R). Given that one of them does not exist it has a strahler number of 0, and so the parent takes the strahler number of its only child.
If the strahler numbers of both of the children are the same, then the parent is assigned a strahler number of either of the children plus 1. The strahler number of the tree is the strahler number of the root.
Let's find the strahler number of the following tree:

Leaf nodes are assigned a strahler number of 1. If both of the children have the same strahler number, the parent ends up with the strahler number of either child +1. If the strahler number of the children is not the same, we take the greater of the two. Using this logic, we end up with the following tree (the information of a node is the strahler number for that node).

2. Code

Having understood the recursive definition, the code is quite straightforward. Let us suppose the binary tree is represented with the help of a left and right array like this:

The code for finding a strahler number of a binary tree that is represented by a Left and a Right array as explained above would be the following:

static int strahlerNumber(int currentNode) {   
 int strahlerLeft = 0;   
 int strahlerRight = 0;
 
 if(lt[currentNode] != 0) strahlerLeft = strahlerNumber(lt[currentNode]);   
 else strahlerLeft = 0;   
 
 if(rt[currentNode] != 0) strahlerRight = strahlerNumber(rt[currentNode]);   
 else strahlerRight = 0;
 
 if(strahlerLeft != strahlerRight) 
  strahler[currentNode] = Math.max(strahlerLeft, strahlerRight);   
 else strahler[currentNode] = strahlerLeft+1;
 
 return strahler[currentNode];   
}

3. The Program

You can download the program from here. The program is a jar file, run it from the command line (java -jar strahler.jar). The program does not contain the source code. What the program does is that given the number of nodes, it is going to generate all the possible unique binary trees with n nodes in reverse lexicographic order (starting from a left chain and shifting all the nodes right, till we get a right chain), it is going to print out each tree in L and R array representation as above, and it is going to print out the strahler number for each generated tree.
The number of binary trees are actually the Catalan numbers: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845 ...
Here is the output of running the program for 4 nodes:

~~~~~~ BUILDING BINARY TREES WITH 2 NODES ~~~~~~

===: TREE: 1 ===
L[1]=2, R[1]=0
L[2]=0, R[2]=0
1100
Strahler number: 1

===: TREE: 2 ===
L[1]=0, R[1]=2
L[2]=0, R[2]=0
1010
Strahler number: 1

 ====== 2 trees for 2 nodes ======

~~~~~~ BUILDING BINARY TREES WITH 3 NODES ~~~~~~

===: TREE: 1 ===
L[1]=2, R[1]=0
L[2]=3, R[2]=0
L[3]=0, R[3]=0
111000
Strahler number: 1

===: TREE: 2 ===
L[1]=2, R[1]=0
L[2]=0, R[2]=3
L[3]=0, R[3]=0
110100
Strahler number: 1

===: TREE: 3 ===
L[1]=2, R[1]=3
L[2]=0, R[2]=0
L[3]=0, R[3]=0
110010
Strahler number: 2

===: TREE: 4 ===
L[1]=0, R[1]=2
L[2]=3, R[2]=0
L[3]=0, R[3]=0
101100
Strahler number: 1

===: TREE: 5 ===
L[1]=0, R[1]=2
L[2]=0, R[2]=3
L[3]=0, R[3]=0
101010
Strahler number: 1

 ====== 5 trees for 3 nodes ======

~~~~~~ BUILDING BINARY TREES WITH 4 NODES ~~~~~~

===: TREE: 1 ===
L[1]=2, R[1]=0
L[2]=3, R[2]=0
L[3]=4, R[3]=0
L[4]=0, R[4]=0
11110000
Strahler number: 1

===: TREE: 2 ===
L[1]=2, R[1]=0
L[2]=3, R[2]=0
L[3]=0, R[3]=4
L[4]=0, R[4]=0
11101000
Strahler number: 1

===: TREE: 3 ===
L[1]=2, R[1]=0
L[2]=3, R[2]=4
L[3]=0, R[3]=0
L[4]=0, R[4]=0
11100100
Strahler number: 2

===: TREE: 4 ===
L[1]=2, R[1]=4
L[2]=3, R[2]=0
L[3]=0, R[3]=0
L[4]=0, R[4]=0
11100010
Strahler number: 2

===: TREE: 5 ===
L[1]=2, R[1]=0
L[2]=0, R[2]=3
L[3]=4, R[3]=0
L[4]=0, R[4]=0
11011000
Strahler number: 1

===: TREE: 6 ===
L[1]=2, R[1]=0
L[2]=0, R[2]=3
L[3]=0, R[3]=4
L[4]=0, R[4]=0
11010100
Strahler number: 1

===: TREE: 7 ===
L[1]=2, R[1]=4
L[2]=0, R[2]=3
L[3]=0, R[3]=0
L[4]=0, R[4]=0
11010010
Strahler number: 2

===: TREE: 8 ===
L[1]=2, R[1]=3
L[2]=0, R[2]=0
L[3]=4, R[3]=0
L[4]=0, R[4]=0
11001100
Strahler number: 2

===: TREE: 9 ===
L[1]=2, R[1]=3
L[2]=0, R[2]=0
L[3]=0, R[3]=4
L[4]=0, R[4]=0
11001010
Strahler number: 2

===: TREE: 10 ===
L[1]=0, R[1]=2
L[2]=3, R[2]=0
L[3]=4, R[3]=0
L[4]=0, R[4]=0
10111000
Strahler number: 1

===: TREE: 11 ===
L[1]=0, R[1]=2
L[2]=3, R[2]=0
L[3]=0, R[3]=4
L[4]=0, R[4]=0
10110100
Strahler number: 1

===: TREE: 12 ===
L[1]=0, R[1]=2
L[2]=3, R[2]=4
L[3]=0, R[3]=0
L[4]=0, R[4]=0
10110010
Strahler number: 2

===: TREE: 13 ===
L[1]=0, R[1]=2
L[2]=0, R[2]=3
L[3]=4, R[3]=0
L[4]=0, R[4]=0
10101100
Strahler number: 1

===: TREE: 14 ===
L[1]=0, R[1]=2
L[2]=0, R[2]=3
L[3]=0, R[3]=4
L[4]=0, R[4]=0
10101010
Strahler number: 1

 ====== 14 trees for 4 nodes ======