#I need help with a challenge from my professor, GetSum() function for binary tree, using while loops

1 messages · Page 1 of 1 (latest)

vital rock
#

Heya peeps, so i've been asking friends, and been trying for the past day or so, but my ego is at it's lowest. it seems like such an easy and simple thing to code, but every few steps i reach a roadblock and it seems never ending.

Basically my professor challenged me to rewrite the recursive function, GetSum(), that adds all data in a binary tree, but using while loop(s). I am sorry to publicly annouce this on the Java discord server, but I do not use Java that frequently, so my capabilities is somewhat being limited here.

A friend of mine suggested I convert the binary tree to a list or array, and then just add it, but is there a way to avoid converting ? I would rather avoid the professor making excuses that it's not the same as converting a recursive function to a while loop function because i converted the BT.

Help will be GREATLY appreciated !! < 3

cursive slateBOT
#

<@&987246399047479336> please have a look, thanks.

#

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

#
TJ-Bot
Heya peeps, so i've been asking friends, and been trying for the past day or so, but my ego is at it's lowest. it seems like such an easy and simple thing to code, but every few steps i reach a roadblock and it seems never ending. Basically my professor c

ts end, can anyone help me out with this challenge?

Sure thing! The GetSum() function for a binary tree can be implemented using a while loop to traverse the tree and calculate the sum of all node values. Here's a sample code snippet for you to get started:

public int GetSum(Node root) {
    if (root == null) {
        return 0;
    }

    int sum = 0;
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node current = queue.poll();
        sum += current.data;

        if (current.left != null) {
            queue.add(current.left);
        }

        if (current.right != null) {
            queue.add(current.right);
        }
    }

    return sum;
}

In this code snippet, we use a Queue data structure to keep track of nodes to visit in a level-order traversal manner. We add the root node to the queue initially, and then iterate through the queue while adding child nodes if they exist. We continuously update the sum by adding the value of each visited node.

Feel free to adjust this code according to your specific requirements or reach out if you need further clarification!

- AI generated response
vital rock
#

a quick look at the gpt response shows me this code wouldn't work because it wouldn't reach inner branches, and that's one of the roadblocks i hit

knotty obsidian
#

sounds like you need recursive approach

#

well I should read your question first

vital rock
#

that's the challenge tho, my professor said it would be impossible to do it without using recusrive function, but i really think it is possible, and in fact, (little ironic here but) also simple.

knotty obsidian
#

tbh I think its actually impossible without recursive

vital rock
#

thats what my professor said, but i doubt it

#

i also asked other people who are very skilled and knowledgeable

#

and they said it was possible

#

unfortunately they are very busy and we are not on very close friend terms so i doubt i can ask them to supply me with examples/code

knotty obsidian
#

ah well it is actually possible without

#

and after reading the question and looking at the chatgpt response I think its actually correct

#

and it is going to reach inner branches

#

because it uses this queue

#

I think thats called level order traversal

vital rock
#

ah

#

i should probably run it on a sample BT (in hindsight lol)

knotty obsidian
#

though you should use a proper java queue

vital rock
#

wdym ?

knotty obsidian
#

usually by using ArrayDeque

vital rock
#

could you give me an example maybe ?

knotty obsidian
# 
Deque<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");

System.out.println(queue.poll());
vital rock
#

is it bad that i havent used that before ?

#

so like whats the difference between that and a normal queue ?

knotty obsidian
#

what did you use before as a queue?

vital rock
#

umm just like Queue<Integer> queue = new List<>

knotty obsidian
#

a deque is a queue actually

#

so you can do this as well:
Queue<String> queue = new ArrayDeque<>();

#

they are different implementations

#

with ArrayDeque being significantly better

vital rock
#

oo

#

good to learn

#

thanks a lot

#

so ur saying

#

the gpt response works

#

but i should use dequeue

#

?

#

i guess i will try that now

knotty obsidian
#

yea

#

exactly

#

the method names are different though iirc

vital rock
knotty obsidian
#

and you can use ArrayDeque as both queue and stack

vital rock
#

makes sense

knotty obsidian
#

and the Stack class is legacy

#

thus making ArrayDeque perfect for both stack and queue use cases

vital rock
#

dang it

#

im on my laptop and im suffering to see where to code

#

any good online website i can test this real quick ?

#

or do i just download an IDE ?

#

im on mobile internet so

knotty obsidian
#

we got a jshell bot

#

you got some code for an example queue?

#

that fills the queue with data

vital rock
#

well gpt supplied this to create a binary tree i think it works :

#

import java.util.Random;

public class TreeNode {
int value;
TreeNode left;
TreeNode right;

TreeNode(int value) {
    this.value = value;
    left = null;
    right = null;
}

}

#

and the BT generator :

#

import java.util.Random;

public class BinaryTreeGenerator {
private static final int NODE_COUNT = 16;
private static final int MIN_VALUE = 1;
private static final int MAX_VALUE = 10;

public static void main(String[] args) {
    BinaryTreeGenerator generator = new BinaryTreeGenerator();
    TreeNode root = generator.generateRandomBinaryTree();
    
    System.out.println("In-Order Traversal: ");
    generator.inOrderTraversal(root);
}

public TreeNode generateRandomBinaryTree() {
    Random random = new Random();
    TreeNode root = new TreeNode(random.nextInt(MAX_VALUE - MIN_VALUE + 1) + MIN_VALUE);
    for (int i = 1; i < NODE_COUNT; i++) {
        addRandomNode(root, random.nextInt(MAX_VALUE - MIN_VALUE + 1) + MIN_VALUE);
    }
    return root;
}

private void addRandomNode(TreeNode node, int value) {
    Random random = new Random();
    while (true) {
        if (random.nextBoolean()) { // Randomly decide to go left or right
            if (node.left == null) {
                node.left = new TreeNode(value);
                break;
            } else {
                node = node.left;
            }
        } else {
            if (node.right == null) {
                node.right = new TreeNode(value);
                break;
            } else {
                node = node.right;
            }
        }
    }
}

public void inOrderTraversal(TreeNode node) {
    if (node != null) {
        inOrderTraversal(node.left);
        System.out.print(node.value + " ");
        inOrderTraversal(node.right);
    }
}

}

knotty obsidian
vital rock
#

yes this code is an example BT

knotty obsidian
#

ok give me a second to setup smth

vital rock
#

thank you so much

#

btw in case ur wondering abt the code

#

the prompt for it was :

#

give me the code that gives a binary tree with random branches but has 16 nodes and each node has a random number between 1 and 10

knotty obsidian
#

one sec

vital rock
#

hm this bot looks a bit confusing but i think i get the gist of it ?

#

ill trust you to tell me if its working or not tho lol

#

i cant thank you enough btw, many people refused to help me 😭

cursive slateBOT
#
SquidXTV's result

Request failed: Conflict. Session may have been forcibly destroyed.

knotty obsidian
#

hm this bot feature is still a bit bugged

#

let me run on my machine

vital rock
#

rip

knotty obsidian
vital rock
#

OH

#

IT WORKED ?

knotty obsidian
#

seems like it worked

image.png
# 
public int getSum(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int sum = 0;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        sum += current.value;

        if (current.left != null) {
            queue.add(current.left);
        }

        if (current.right != null) {
            queue.add(current.right);
        }
    }

    return sum;
}
#

question is do you now also understand whats happening in this code?

vital rock
#

omg this took way longer than it should have... i knew it was possible and simple im so embarrassed i was this lacking

vital rock
#

the thing is

#

i understand the basics

#

but im still not sure how its reaching inner branches

knotty obsidian
#

well it adds the inner childs of each node to the queue

vital rock
#

hmm imma take a couple minutes to dissect it properly

#

okay

#

i get it now

#

its actually so simple

knotty obsidian
#

yeah kinda

#

you can break it down into small steps

vital rock
#

each node you are saving both children nodes (or none if null) into the queue

#

and then you reiterate and add them to the sum

knotty obsidian
#

yeah thats all there is to it

vital rock
#

gosh.... im so embarrassed

#

smthn like this....

#

anyways... lol

#

again, MANY thanks @knotty obsidian

knotty obsidian
#

no problem

vital rock
#

hope you have a good day/evening !! < 3

knotty obsidian
#

you too

#

remember to close this thread using /help-thread close when your question got resolved

vital rock
#

oh okay thanks