I need to create a recursive method that takes as a parameter the root node of a binary search tree. This recursive method will then return the int value of the total number of nodes in the entire binary search tree.

This is what I have so far:

```
public class BinarySearchTree<E> extends AbstractSet<E>
{
protected Entry<E> root;
//called by the main method
public int nodes()
{
return nodes(root);
}
//nodes() will count and return the nodes in the binary search tree
private int nodes(Entry<E> current)
{
if(current.element != null)
{
if(current.left == null && current.right == null)
{
if(current.element == root.element)
return 1;
deleteEntry(current);
return 1 + nodes(current.parent);
}
else if(current.left != null && current.right == null)
return nodes(current.left);
else if(current.left == null && current.right != null)
return nodes(current.right);
else if(current.left != null && current.right != null)
return nodes(current.left) + nodes(current.right);
} else return 1;
return 0;
}
```

The main method calls nodes like so:

```
System.out.println ("\nThis section finds the number of nodes "
+ "in the tree");
System.out.println ("The BST has " + bst.nodes() + " nodes");
```

So I was running the search by traveling in order, once I'd get to a node with no children I would delete the current node and return to the parent node and continue. I ran a debug of the method I have above and the program crashes with a NullPointerException() when it finally counts and removes all the nodes on the left and right side of the root node and tries to return 1.

This is for my lab, the method MUST be recursive.

I'm very lost at this point, does anyone know what I'm doing wrong?

After you delete `current`

in: `deleteEntry(current);`

, you use `current.parent`

in `return 1 + nodes(current.parent);`

May be this's the reason of throwing NullPointerException..

You have several issues:

- You're deleting nodes as you count them? Is
`nodes()`

supposed to clear the tree? - You're treating
`root==null`

,`root!=null&left==null&&right==null`

,`root!=null&left!=null&right==null`

, etc as separate cases. They're not. You have three cases, which are not entirely exclusive:- If the current node is not null, add one to the count. (This should always be the case. The only case where it might be false is if the current node ==
`root`

, and we can detect and sidestep that beforehand.) - If the current node has a left child, add the left child's count.
- If the current node has a right child, add the right child's count.

- If the current node is not null, add one to the count. (This should always be the case. The only case where it might be false is if the current node ==
- You're traversing back
*up*the tree for some ungodly reason. Looks like it has something to do with deleting nodes...?

But the biggest thing in my opinion is, you're not giving enough autonomy to the `Entry`

s. :P

A node can count its own children. Trust it to.

```
class Entry<E> {
...
int count() {
int result = 1;
if (left != null) result += left.count();
if (right != null) result += right.count();
return result;
}
}
public int nodes() {
return (root == null) ? 0 : root.count();
}
```

If your teacher is incompetent, and *insists* on some node-counting function outside a node, you can do the same thing you were trying to do:

```
private int nodes(Entry<E> current) {
int result = 1;
if (current.left) result += nodes(current.left);
if (current.right) result += nodes(current.right);
return result;
}
public int nodes() {
return (root == null) ? 0 : nodes(root);
}
```

But that teacher should be fired, in my opinion. The `Entry`

class is the *real* tree; `BinarySearchTree`

is really just a container for a reference to the root.

Also notice, i don't give a damn about the `parent`

s. If we start counting from the root, and each node counts its children, which count their children, etc etc... then all nodes will be accounted for.

You are making this way too complicated. The basic idea of object oriented programming is that you trust objects to do the jobs they know the answers to. So if I'm a parent, I can count myself, and I let my children count themselves, and so forth.

```
private int nodes(Entry<E> current) {
// if it's null, it doesn't exist, return 0
if (current == null) return 0;
// count myself + my left child + my right child
return 1 + nodes(current.left) + nodes(current.right);
}
```

Hey I have a very clean counting implemented for a binary tree:

```
public class Binary<T> where T: IComparable<T>
{
private Node _root;
public int Count => _root.Count;
public void Insert(T item)
{
Node newNode = new Node(item);
if (_root == null)
_root = newNode;
else
{
Node prevNode = _root;
Node treeNode = _root;
while (treeNode != null)
{
prevNode = treeNode;
treeNode = newNode.Item.CompareTo(treeNode.Item) < 1 ? treeNode.Left : treeNode.Right;
}
newNode.Parent = prevNode;
if (newNode.Item.CompareTo(prevNode.Item) < 1)
prevNode.Left = newNode;
else
prevNode.Right = newNode;
}
}
public class Node
{
public T Item;
public Node Parent;
public Node Left;
public Node Right;
public Node(T item, Node parent = null, Node left = null, Node right = null)
{
Item = item;
Parent = parent;
Left = left;
Right = right;
}
public int Count
{
get
{
int count = 1;
count += Left?.Count ?? 0;
count += Right?.Count ?? 0;
return count;
}
}
}
}
```

Maybe this helps you to understand how to implement a class for a simple binary tree with a count.

This implementation accesses the count through a count in the corresponding node in the tree.

Let me now if you are not familiar with the markup of .NET 4.6

```
public int countNodes(Node root){
// empty trees always have zero nodes
if( root == null ){
return 0;
}
// a node with no leafes has exactly one node
// note from editor: this pice of code is a micro optimization
// and not necessary for the function to work correctly!
if( root.left == null && root.right == null ){
return 1;
}
// all other nodes count the nodes from their left and right subtree
// as well as themselves
return countNodes( root.left ) + countNodes( root.right ) + 1;
}
```

Similar Questions

I have managed to create a threaded binary search tree through it's insertion method. I now need to traverse the tree and print in order. I have code that works, but I used an boolean flag to determin

I want to create all possible topologies of a full binary tree which must have exactly n+1 leaf nodes and n internal nodes. I want to create it using recursion and tree must be simple binary tree not

I'm currently working on a school project. The assignment is to write the implementation of a templated binary search tree given the corresponding header file. My issue is that since it's templated,

I wrote an insert method for a binary search tree that is void. I have to change that method so that it returns a boolean but I am confused because my helper method for insert returns a Node. Is there

Which is the following data structures be best suited for insertion, deletion, lookup, set intersection, union? Optimize time complexity. Bitmaps Binary search tree

I'm writing a binary tree class, and I'm stuck on a levelCount method, where I need to count the number of nodes on a level of the tree. The class and method look something like this: public class Con

Alrighty, so I wrote up a binary search tree, and I'm putting it up here, the whole code (not like it's hard to find the code for this online anyways...) in the hopes that someone can find my slight e

I'm getting a problem with my display functions dealing with binary search trees. The main problem I'm having is getting the count variable to increment correctly in the recursive function so that I c

Please help I've been trying to generate a random binary search tree of size 1024 and the elements needs to be random sortedset ... I'm able to write a code to create a binary search tree manually by

I would like to calculate the summation of the depths of each node of a Binary Search Tree. The individual depths of the elements are not already stored.

So when i delete in binary search tree, do i need to have like 7 different cases i.e. 1.Left Leaf; 2.Right Leaf; 3.Left child with only left child.//i.e the node to be deleted is the left child of it'

Given a binary tree with nodes having color attribute. The tree has red nodes and blue nodes. Remove all blue nodes from the tree and return a tree with only the red nodes? I have tried to implement t

i am constructing the operations of binary search tree in OCaml. type ('a, 'b) bst = | Node of 'a * 'b * ('a, 'b) bst * ('a, 'b) bst | Leaf;; let rec insert k v = function | Leaf -> Node (k, v, Lea

This question already has an answer here: Binary search tree insertion - root always null 1 answer I am making a basic binary search tree and its operations. Why isn't my insert working? It is

I adapted my code from from this book: Data Structures and Algorithms by Mark Allen Weiss, 3rd edition. Every time I run it, it crashes. By request I'll add the entire Binary Tree code(its long). Whe

This is a binary search tree implementation, I cant figure out why my min method (for finding the minimum element in a tree) is not returning the correct answer, but an arbitrary memory address. I am

I read on here of an exercise in interviews known as validating a binary search tree. How exactly does this work? What would one be looking for in validating a binary search tree? I have written a bas

You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which

I am implementing code to construct BST(binary search tree) from a given post-order traversal array following this algorithm. I do not get back the binary Search Tree back. I am getting something that

I am getting confused on my binary search algorithm. I have to insert the following integers into an empty binary tree in the given order using put(): 4,1,3,5,2. Im not 100 percent sure if I went abou

I'm learning Data Structures & Algorithms now. My lecture notes have an implementation of a binary search tree which is implemented using a recursive method. That is an elegant way, but my questio

I am having a difficult time understanding how binary search trees are built. Do they require the initial data to be sorted in order to find the top most root?

Got nothing better to do this Christmas holiday, so I decided to try out making a binary search tree. I'm stuck with the print function. How should the logic behind it work? Since the tree is already

I've been working on implementing a binary search tree in C for a homework assignment in my programming class. After writing this much of the code and compiling in Visual Studio 2010, I get numerous e

i have implement binary search tree in c++ #include <iostream> #include <cstdlib> using namespace std; class binary{ private: struct tree{ tree *left; tree *right; int data; }; tree *root;

I'm working on a problem which requires me to copy a binary search tree recursively and to return the tree. I am coding in the binary search tree class, so it will copy whatever binary search tree it

for my coursework(binary search tree and hashtables) I would like to make a java program that scans a text file and orders words based on the most frequent words. Something like most popular tags. Exa

I am working on Binary search tree and I am having some problems in updating/adding the parent node of current node.Parent node are not getting updated correctly.This is what Iam trying to do: public

Im trying to build an array based, Binary Search Tree by following the algorithm at: http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif%3A:600%3A:388%3A%3A/sites/dl/free/0070131511/2532

I am having trouble counting the nodes in my binary tree. It is a real simple tree to start as illustrated in the diagram below. (5) (3)-------^-------(7) (2)---^---(6) ^-------(9) (5)---^---(8) I

I have a working search function that will search for the exact value in a database, but my goal is for it to search for substrings in the database of the stored data and when searching for substrings

The question is to find out sum of distances between every two nodes of BinarySearchTree given that every parent-child pair is separated by unit distance. It is to be calculated after every insertion.

I've been stuck on the insertion part of the binary search tree. I get so confused with nested structs. The basic idea of this program is to create a bst that is able to hold names and double values w

Can anyone please explain the difference between binary tree and binary search tree with an example?

Search(T,k) x<- root[T] while x != NULL and k != key[x] do if k<key[x] then x <- left[x] else x <- right[x] return x I just started with algorithms and I often see <- this and key[x]

I need help in 3 tasks. I'm really new in Haskell and functional programming. data Tree = Node Int Tree Tree | Nil Define with help of the function collapse collapse :: Tree -> [Int] collapse N

What is the benefit of a binary search tree over a sorted array with binary search? Just with mathematical analysis I do not see a difference, so I assume there must be a difference in the low-level i

For an assignment we were given in Data Structures, we had to create a test class to determine whether the code we were given correctly traversed the binary trees in our test class. These are the 3 co

I have a binary search tree consists of nodes like : struct ProductNode { Product data; ProductNode* left; ProductNode* right; }; and i have a delete function that takes ProductNode pointer parameter

I'm looking for a way to select from a binary tree (AVL or B tree) using Lambda without running through all the nodes in the tree. Any suggestions or interesting links?

Context: I am building a FoundationDB, and I am thinking about which key use first Let's say we have this set of elements : {AP,AQ,AR,BP,BQ,BR} and we want to build a tree from it. One way is to gro

I define a binary tree as a search table. The tree is a linked list binary tree, the node is like typedef struct node{ int key; char *buf; ... }node_t; typedef table_t node_t *; so I have functions l

having a bit of problems with my insert function here. It compiles fine but if I try to add a 4th node it just replaces one of the first child nodes instead of adding a new one to those child nodes..

I am working with a binary search tree in Python 3.2.3 and here are my two files (given from teacher) for creating the binary search tree. But first I will explain the problem I am having. First I am

I want to search for an item in non-binary tree (any node can have n - children) and exit from recursion immediately. The node in question can be any node, not only leafs. This is my code but i don't

This is Exercise 15.5-4 of Introduction to Algorithms, 3rd edition, which is about Knuth's improvement to the DP approach to Optimal Binary Search Tree. The DP algorithm of Optimal Binary Search Tree

I would like to find the most efficent way to check the node with minimum value in a Binary Search Tree. I'm not thinking to do it in a certain programming language right now, I would like just to thi

I am new on C++. My background is from PHP and C#. I implement Binary search tree in VC++ in Visual Studio 2005 All operations are fine, I am facing the problem with delete in one particular scenario,

For inorder binary search tree traversal there is an iterative algorithm that uses no auxiliary memory (stack, parent pointers, visited flags) known as Morris Traversal. Is there a similar algorithm f

I was trying to implement a simple Binary Search Tree for practice. I tried to just add values and print the values in the nodes. However, I am not getting the proper ascending order of values in the