Hello!

Today we will look at simple algorithm that can find node depth in tree. As input to the script given tree and the depth of the tree must be returned. Node depth is the sum of the depths of all nodes.

For example, take a tree

        6
       / \
      4  10
     / \   \
    2   5   23
   /
  3

The depth of the root is always 0, and the next elements will always be the depth of the previous element +1. Then we will have

        6 - 0
       / \
  1 - 4  10 - 1
     / \   \
    2   5   23
   /
  3

            6 - 0
           / \
      1 - 4  10 - 1
         / \   \
    2 - 2   5 - 2  23 - 2
       /
      3

            6 - 0
           / \
      1 - 4  10 - 1
         / \   \
    2 - 2   5 - 2  23 - 2
       /
  3 - 1

Having the depth of all the elements and adding them we get the depth of the tree. 0 + 1 + 1 + 2 + 2 + 2 + 3 = 11. Thus the depth of the tree is 11.

Example code on golang

package main

import "fmt"

type Tree struct {
	root *Node
}

type Node struct {
	key   int
	left  *Node
	right *Node
}

func main() {
	tree := Tree{
		&Node{
			key: 5,
			left: &Node{
				key: 4,
				left: &Node{
					key: 3,
				},
			},
			right: &Node{
				key: 10,
				right: &Node{
					key: 13,
				},
			},
		},
	}
	fmt.Println(nodeDepth(tree.root, 0))
}

func nodeDepth(node *Node, depth int) int {
	if node == nil {
		return 0
	}
	return depth + nodeDepth(node.left, depth+1) + nodeDepth(node.right, depth+1)
}