Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Number of Full Nodes in a Binary Tree

Explore how to identify and count full nodes in a binary tree through recursive traversal. This lesson helps you understand node definitions, implement the solution in Go, and analyze its time complexity as O(n). You will gain practical skills in working with tree structures and recursive algorithms.

We'll cover the following...

Solution

A full node is a node that has both left and right children. We’ll recursively traverse the whole tree and will increase the count of full nodes as we find them.

Code

Go (1.6.2)
package main
import "fmt"
func (t *Tree) NumFullNodesBT() int {
    return numFullNodesBT(t.root)
}
func numFullNodesBT(curr *Node) int {
    var count int
    if curr == nil {
        return 0
    }
    count = numFullNodesBT(curr.right) + numFullNodesBT(curr.left)
    
    if curr.right != nil && curr.left != nil {
        count++
    }
    return count
}
/* Testing Code */
func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    t := LevelOrderBinaryTree(arr)
    fmt.Println(t.NumFullNodesBT())
}

Time complexity

...