Sum of alternate leaf nodes in bst

In this article, we will discuss the problem of finding the sum of alternate leaf nodes in a Binary Search Tree (BST). We will explain the problem statement, provide a suitable example, present the algorithm and pseudocode, and analyze the time complexity of the code. Let's dive in!

Here given code implementation process.

Problem Statement

Given a Binary Search Tree, we need to find the sum of the alternate leaf nodes in the tree. The alternate leaf nodes are the leaf nodes that occur at alternate levels in the tree.

Example

Consider the following Binary Search Tree:

		       5
		      /  \  
		     /    \ 
		    /      \
		   3        19
		  / \     /   \
		 2   4   8     31
		       / \    / \
		      7   15 25  50  

In this example, the alternate leaf nodes are 2, 4, 7, 15, 25, and 50. The sum of these alternate nodes is 2 + 7 + 25 = 34.

Algorithm

To solve this problem, we can use a recursive approach. Here's the algorithm:

1. Create a structure for the tree node, which consists of the node's data, and pointers to its left and right child nodes.
2. Create a structure for the Binary Search Tree (BST), which consists of a pointer to the root node of the tree and an alternate flag.
3. Create a function to add a new node to the BST:
1. Create a new node with the given data.
2. If the root of the BST is empty, set the new node as the root.
3. Otherwise, traverse the BST to find the appropriate position for the new node.
4. If the data of the new node is less than or equal to the current node, go to the left child. If the left child is empty, set the new node as the left child. Otherwise, continue traversing the left subtree.
5. If the data of the new node is greater than the current node, go to the right child. If the right child is empty, set the new node as the right child. Otherwise, continue traversing the right subtree.
4. Create a function to calculate the sum of alternate leaf nodes:
1. If the current node is not null:
1. If the current node is a leaf node (both left and right children are null):
1. Toggle the alternate flag in the BST structure.
2. If the alternate flag is true, return the data of the current node (as it is an alternate leaf node).
2. Otherwise (if the current node is an internal node), recursively call the function for the left and right child nodes and return the sum of their results.
2. If the current node is null, return 0.
5. Create a function to calculate the sum of alternate leaf nodes in the BST:
1. Reset the alternate flag to 0.
2. Call the leafSum function with the root of the BST and return the result.
6. In the main function:
1. Create a Binary Search Tree.
2. Add nodes to the tree.
3. Call the alternateLeafSum function and print the result.

Pseudocode

Structure TreeNode:
    Integer data
    TreeNode left
    TreeNode right

Function getTreeNode(data):
    Create a new TreeNode
    Set the data of the TreeNode to the given data
    Set the left and right pointers to NULL
    Return the new TreeNode

Structure BinarySearchTree:
    TreeNode root
    Integer alternate

Function getBinarySearchTree():
    Create a new BinarySearchTree
    Set the root to NULL
    Set the alternate flag to 0
    Return the new BinarySearchTree

Function addNode(ref, data):
    Create a new node with the given data
    If the root of ref is NULL:
        Set the new node as the root
    Else:
        Set find as the root of ref
        While find is not NULL:
            If find's data is greater than or equal to the data:
                If find's left child is NULL:
                    Set the new node as find's left child
                    Return
                Else:
                    Set find as find's left child
            Else:
                If find's right child is NULL:
                    Set the new node as find's right child
                    Return
                Else:
                    Set find as find's right child

Function leafSum(ref, node):
    If node is not NULL:
        If node is a leaf node (both left and right children are NULL):
            Toggle the alternate flag in ref
            If the alternate flag is true:
                Return the data of the node
        Else:
            Return leafSum(ref, node's left child) + leafSum(ref, node's right child)
    Return 0

Function alternateLeafSum(ref):
    Reset the alternate flag to 0 in ref
    Return leafSum(ref, ref's root)

Main function:
    Create a BinarySearchTree
    Add nodes to the tree
    Print the result of alternateLeafSum

Solution

1) Sum of alternate leaf nodes in bst in java 2) Sum of alternate leaf nodes in bst in c++ 3) Sum of alternate leaf nodes in bst in c 4) Sum of alternate leaf nodes in bst in c# 5) Sum of alternate leaf nodes in bst in php 6) Sum of alternate leaf nodes in bst in node js 7) Sum of alternate leaf nodes in bst in typescript 8) Sum of alternate leaf nodes in bst in python 9) Sum of alternate leaf nodes in bst in ruby 10) Sum of alternate leaf nodes in bst in scala 11) Sum of alternate leaf nodes in bst in swift 12) Sum of alternate leaf nodes in bst in kotlin 13) Sum of alternate leaf nodes in bst in golang 14) Sum of alternate leaf nodes in bst in vb.net

Result and Time Complexity

Running the given code with the provided example BST will yield an output of 34, which is the sum of the alternate leaf nodes.

The time complexity of the code is O(n), where n is the number of nodes in the BST. This is because we traverse each node exactly once while adding nodes to the tree and calculating the sum of alternate leaf nodes.

That concludes our explanation of the problem, algorithm, pseudocode, and output. By following the presented steps, you can find the sum of alternate leaf nodes in a Binary Search Tree using the provided code.