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

Solution Review: Is Tree a Heap

Explore how to determine if a given tree is a min heap by checking its completeness and the parent node values in relation to its children. Understand two methods that traverse the tree recursively and efficiently, ensuring the heap properties hold. Gain insights on the implementation and time complexity for robust coding in Go.

We'll cover the following...

Solution

To see if the given tree is a heap, we need to check the following conditions:

  1. It is a complete tree.
  2. The value of a parent node is smaller than or equal to its left and right child.

We can check these conditions using the following two methods.

First method

The first method is to test if a given tree is complete and if the parent-child property is followed. If a tree is a complete tree and all parent nodes in the tree have a value less than or equal to its children, this tree represents a min heap.

Solution code

Go (1.6.2)
package main
import "fmt"
func (t *Tree) IsHeap() bool {
    parentValue := -99999999
    return t.IsCompleteTree() && isHeapUtil(t.root, parentValue)
}
func isHeapUtil(curr *Node, parentValue int) bool {   
    if (curr == nil){
        return true
    }
    if (curr.value < parentValue){
        return false
    }
    return isHeapUtil(curr.left, curr.value) && isHeapUtil(curr.right,
    curr.value)
}
/* Testing Code */
func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    t := LevelOrderBinaryTree(arr)
    fmt.Println(t.IsHeap());
}

Time complexity

The isCompleteTree() ...