Explain the mechanism of searching for an element in a binary tree and how its traversal is performed.

In a binary search tree (BST), the search for an element proceeds as follows:

1. Start from the root of the tree.
2. Compare the desired value with the current node:
   • If the value is equal, the element is found.
   • If the value is less, move to the left subtree.
   • If the value is greater, move to the right subtree.
3. Repeat the process until the element is found or an empty node is reached (element not present).

Tree traversal is a method of visiting all nodes in sequence. The main types of traversal are:

• In-order (symmetric): left subtree → node → right subtree. It allows obtaining elements in sorted order.
• Pre-order (direct): node → left subtree → right subtree.
• Post-order (reverse): left subtree → right subtree → node.

Example of search and traversal in Go:

package main
import "fmt"

type Node struct {
    Value int
    Left, Right *Node
}

func (n *Node) Search(val int) *Node {
    if n == nil || n.Value == val {
        return n
    }
    if val < n.Value {
        return n.Left.Search(val)
    }
    return n.Right.Search(val)
}

func (n *Node) InOrder() {
    if n == nil {
        return
    }
    n.Left.InOrder()
    fmt.Print(n.Value, " ")
    n.Right.InOrder()
}

func main() {
    root := &Node{Value: 10}
    root.Left = &Node{Value: 5}
    root.Right = &Node{Value: 15}

    node := root.Search(5)
    if node != nil {
        fmt.Println("Found node with value:", node.Value)
    } else {
        fmt.Println("Element not found")
    }

    fmt.Print("In-order traversal: ")
    root.InOrder() // Will output: 5 10 15
}