Setting an index of a binary tree in go

Question

Im trying to teach myself data structures & algos and I am trying to figure out the best way to add an index to a binary tree

Im guessing the best way to do this is to modify an in orderTraversal operation but im not exactly sure how I would implement this and chain that on after every insert and delete function.

type BinarySearchNode struct {
    Left *BinarySearchNode
    Right *BinarySearchNode
    Parent *BinarySearchNode
    Data int
    Index int
}

func (BSN *BinarySearchNode) Insert(value int){
    
    if BSN.Data > value {
        if BSN.Left == nil{
            BSN.Left = &BinarySearchNode{Data:value, Parent:BSN}
            return
        }
        BSN.Left.Insert(value)
        return
    }

    if BSN.Right == nil{
        BSN.Right = &BinarySearchNode{Data:value, Parent: BSN}
        return
    }
    BSN.Right.Insert(value)
}

func (BSN *BinarySearchNode) setIndex(node *BinarySearchNode, count int)(int){
    if node == nil{
        return count
    }

    if node.Right == nil && node.Left == nil{
        node.Index = count
    }
    node.setIndex(node.Left, count+1)
    node.setIndex(node.Right, count+1)
    
    return count
}

Answer 1

I have a piece of code for the implementation of binary tree in golang. It may help you.

package main

import (
    "fmt"
    "math"
)

// A single Node in a binary tree
type Node struct {

    // Value contained by the node
    Value int

    // Left subnode of the node
    Left *Node

    // Right subnode of the node
    Right *Node
}

type BinaryTree struct {
    Root *Node
}

// inserting the element in the binary tree
func (tree *BinaryTree) Insert(value int) {
    if tree.Root == nil {
        node := new(Node)
        node.Value = value
        tree.Root = node
        return
    }
    current := tree.Root
    for {
        if value < current.Value {
            if current.Left == nil {

                node := new(Node)
                node.Value = value
                current.Left = node
                return
            } else {
                current = current.Left
            }

        } else {
            if current.Right == nil {

                node := new(Node)
                node.Value = value
                current.Right = node
                return
            } else {
                current = current.Right
            }
        }
    }
}

// current left right
func (tree *BinaryTree) RecursivePreOrder(root *Node) {
    if root == nil {
        return
    }
    fmt.Println(root.Value)
    tree.RecursivePreOrder(root.Left)
    tree.RecursivePreOrder(root.Right)

}

func (tree *BinaryTree) IterativePreOrder(root *Node) {
    stack := []*Node{}
    for {
        for root != nil {
            fmt.Println(root.Value)
            stack = append([]*Node{root}, stack...)
            root = root.Left
        }
        if len(stack) == 0 {
            break
        }
        root = stack[0]
        stack = stack[1:]
        root = root.Right
    }
}

func (tree *BinaryTree) RecursiveInOrder(root *Node) {
    if root == nil {
        return
    }
    tree.RecursiveInOrder(root.Left)
    fmt.Println(root.Value)
    tree.RecursiveInOrder(root.Right)

}

func (tree *BinaryTree) IterativeInOrder(root *Node) {
    var stack []*Node
    for {
        for root != nil {
            stack = append([]*Node{root}, stack...)
            root = root.Left
        }
        if len(stack) == 0 {
            break
        }
        root = stack[0]
        stack = stack[1:]
        fmt.Println(root.Value)
        root = root.Right
    }
}

func (tree *BinaryTree) RecursivePostOrder(root *Node) {
    if root == nil {
        return
    }
    tree.RecursivePostOrder(root.Left)
    tree.RecursivePostOrder(root.Right)
    fmt.Println(root.Value)
}

func (tree *BinaryTree) IterativePostOrder(root *Node) {
    stack := []*Node{}

    var previous *Node = nil
    for {
        for root != nil {
            stack = append([]*Node{root}, stack...)
            root = root.Left
        }
        for root == nil && len(stack) != 0 {
            root = stack[0]
            if root.Right == nil || root.Right == previous {
                fmt.Println(root.Value)
                stack = stack[1:]
                previous = root
                root = nil
            } else {
                root = root.Right
            }
        }
        if len(stack) == 0 {
            break
        }
    }
}

func (tree *BinaryTree) LevelOrder(root *Node) {
    // a queue for performing level order traversal of breadth first traversal
    queue := []*Node{}

    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        root = queue[0]
        queue = queue[1:]
        fmt.Println(root.Value)
        if root.Left != nil {
            queue = append(queue, root.Left)
        }
        if root.Right != nil {
            queue = append(queue, root.Right)
        }
    }
}

func (tree *BinaryTree) Size(root *Node) int {
    if root == nil {
        return 0
    }
    sum := tree.Size(root.Left) + 1 + tree.Size(root.Right)
    return sum
}

func (tree *BinaryTree) ElementAt(root *Node, index int) *Node {
    if index > tree.Size(root)-1 {
        fmt.Println("Index doesnot exist")
        return nil
    }
    leftSize := tree.Size(root.Left)
    if index == leftSize {
        return root
    } else if index < leftSize {
        return tree.ElementAt(root.Left, index)
    } else {
        return tree.ElementAt(root.Right, index-leftSize-1)
    }
}

func (tree *BinaryTree) Height(root *Node) int {
    if root == nil {
        return -1
    }
    return int(math.Max(float64(tree.Height(root.Left)), float64(tree.Height(root.Right)))) + 1
}

// starting point of the program
func main() {
    tree := new(BinaryTree)
    tree.Insert(44)
    tree.Insert(55)
    tree.Insert(33)
    fmt.Println(tree.Height(tree.Root))

}