Getting an infinite loop when doing Breadth First Traversal
public void printBreadthFirstTraversal() {
Queue<T> queue = new LinkedList<>();
if (_value == null) {
return;
}
queue.add(_value);
while (!queue.isEmpty()) {
T node = (T) queue.remove();
System.out.print(_value + " ");
if (getLeft() != null) {
queue.add(_left.getValue());
}
if (getRight() != null) {
queue.add(_right.getValue());
}
}
}
The method above is in the class as follows:
public class NonEmpty<T extends Comparable<T>> implements BST<T> {
private T _value;
private BST<T> _left;
private BST<T> _right;
public NonEmpty(T element) {
_left = new Empty<T>();
_right = new Empty<T>();
_value = value;
}
...
// getValue and isEmpty methods written and works
I get an infinite loop when I run a test. It just lists the root value nonstop. What is wrong with my logic here?
See also questions close to this topic

How would you traverse a binary search tree order to update its data? (C PROGRAMMING)
Let's say I have the following Binary search tree and have generated a BST.
Code is in C.
struct BSTNode{ char *name; // key int age; struct BSTNode *left; struct BSTNode *right; }; typedef struct BSTNode *BSTNode;
Now, I want to traverse the tree to update the age for everyone.
void updateAge(BSTNode tree){ (traversal code here) tree>age += 5; }
How would you do that in code?

Rebalancing and rotating in an AVL Tree Implementation
I'm trying to rebalance and also rotate my trees to make a balanced AVL tree. However, I am struggling with my test cases and suspect my rebalance and rotations are off.
private AVLTree<T> rotateLeft() { AVLTree<T> temp = this._right; AVLTree<T> temp1 = temp._left; _right = temp1; temp._left = this; temp.updateHeight(); return temp; } // Similar for Right public SelfBalancingBST<T> insert(T element) { if (isEmpty()) { _element = element; _left = new AVLTree<T>(); _right = new AVLTree<T>(); } else { if (element.compareTo(getValue()) <= 0) { _left = (AVLTree<T>) _left.insert(element); } else if (element.compareTo(getValue()) > 0) { _right = (AVLTree<T>) _right.insert(element); } } this.updateHeight(); return this.rebalance(); } public AVLTree<T> rebalance() { AVLTree<T> tree = this; if (isEmpty()  Math.abs(_left.height()  _right.height())<2) { return tree; } if (_left.height() > _right.height()) { if (_left._right.height() > _left._left.height()) { _left = _left.rotateLeft(); } tree = rotateRight(); } else if (_right.height() > _left.height()) { if (_right._left.height() > _right._right.height()) { _right = _right.rotateRight(); } tree = rotateLeft(); } return tree; } public void updateHeight() { _height = 1 + Math.max(this.getLeft().height(), this.getRight().height()); } public int height() { if (isEmpty()) { return 1; } return _height; }
I'm trying to insert 47, 52, 60, 3, and 7, and am expecting 3, 47, 7, 60, 52 for its post order traversal, but I get 3, 7, 60, 52, 47 (unbalanced) and a height of 5 instead of the expected 2.
I've been staring at this for hours and cannot figure out why. Please help!

BST (Binary Search Tree) element filter function keeps encountering 'NoneType' object
I'm currently stuck on this exercise where I have to filter a binary search tree by returning a list that contains filtered values. This is the exercise:
Given a binary search tree of integers, create a function that will return the elements in a list, where each element
x
satisfies:a <= x < b
, wherea
andb
are parameters provided to the function.filter_bst(tree_node, a, b)
For example, if we insert the values from 0 to 10 into the tree
tree_node
thenfilter_bst(tree_node, a, b)
will return[3,4,5]
.We have this module called
bst.py
(which has the code for binary search tree) in our exercise:class TreeNode(object): """A tree node with two children trees""" def __init__(self, data, parent=None, left=None, right=None): self.data = data self.parent = parent self.left = left self.right = right def search(self, value): """Search in a BST""" if self.data is None: return None if self.data == value: return self if value < self.data: if self.left is None: return None return self.left.search(value) else: if self.right is None: return None return self.right.search(value) def insert(self, value): """insert a node in a BST""" if self.data is None: self.data = value return if value < self.data: if self.left is None: self.left = TreeNode(value, self) else: self.left.insert(value) else: if self.right is None: self.right = TreeNode(value, self) else: self.right.insert(value)
I tried this code, but it isn't working:
import bst def filter_bst(tree_node, a, b): l = [] def filter(tree_node, a, b,l): if tree_node is None: return l # Since the desired output is sorted, recurse for left # subtree first. If tree_node.data is greater than a, then # only we can get output keys in the left subtree if a < tree_node.data: filter(tree_node.left, a, b, l) # If tree_node's data lies in range, then prints its data if a <= tree_node.data and b > tree_node.data: l += [tree_node.data] # If tree_node.data is smaller than b, then only we can get # o/p keys in right subtree if b > tree_node.data: filter(tree_node.right, a, b, l) return filter(tree_node, a, b, l) root = bst.TreeNode(1) root.insert(2) root.insert(3) root.insert(4) root.insert(5) filter_bst(root,2,5)
It's telling me that:
'NoneType' object is not iterable
.PS: I also tried this following code as well but it's also not working:
import bst def filter_bst(tree_node,a,b): l = [] for temp in range(a,b): if tree_node.search(temp) is not None: l += [temp] return l root = bst.TreeNode(1) root.insert(2) root.insert(3) root.insert(4) root.insert(5) filter_bst(root,2,5)
It's telling me that:
'NoneType' object has no attribute 'search'

Traversing through list to free every single Nodes, but still having memory leak
I am writing a linked list in C, when attempting to free every single node, I made a traversal for it. But I am still getting memory leak on this line
newNd = (LinkedListNode*)malloc(sizeof(LinkedListNode));
Here is my insertLast function to insert a node
void insertLast(LinkedList *list, void *entry) { LinkedListNode *newNd = NULL; LinkedListNode *currNd = NULL; /* Creating the newNd */ newNd = (LinkedListNode*)malloc(sizeof(LinkedListNode)); newNd > data = entry; newNd > next = NULL; if( list > head != NULL ) { /* Creating the currNd for traversal */ currNd = list > head; /* Traversal always starts from head */ while( currNd > next != NULL ) /* Stop when we reach the last node */ currNd = currNd > next; currNd > next = newNd; /* Found the last node, and insert newNd with the last node */ list > tail = newNd; /* Set tail pointing towards newNd */ } else { list > head = newNd; list > tail = newNd; } list > count++; /* Increment of count */ }
Here is how i free the list
void freeLinkedList(LinkedList *list, listFunc funcPtr) { /* Removing data of each node */ LinkedListNode *deleteData = NULL; LinkedListNode *deleteNd = NULL; deleteData = list > head; /* Free data (void *) of each node */ while( deleteData != NULL ) { free(deleteData > data); deleteData > data = NULL; deleteData = deleteData > next; } /* Free each node */ deleteNd = list > head; while( deleteNd != NULL ) { list > head = deleteNd > next; free(deleteNd); deleteNd = NULL; deleteNd = list > head; } free(list); list = NULL; }

Serialize and flatten nested JSON tree structure in Javascript
I have an input of a nested json tree structure, I want to process this input to give me an expected output of a flat javascript collection with a "hierarchyPath" property in each object detailing the tree structure relationship of the input format. The object has "limits" and "rules" array of another object with "limits" and "rules" nth deep. basically I want to serialize the tree structure using the id's and indexing the "limits" and "rules" elements.
input
{ "condition":{ "name":"ROOT", "pattern":"" }, "id":0, "limits":[ { "edit_tm": 324234, "editor": "person1", "name": "NAME", "value" :0 } ], "rules":[ { "condition":{ "name":"RANDOM_STATUS", "pattern":"*" }, "edit_tm":1457550081, "editor":"person2", "id":12, "limits":[ { "edit_tm":1457550081, "editor":"person3", "name":"RANDOM_STATUS", "value":50 }, { "edit_tm":1457550081, "editor":"person3", "name":"RANDOM_STATUS", "value":50 }, { "edit_tm":1457550081, "editor":"person4", "name":"RANDOM_STATUS", "value":50 }, { "edit_tm":145755008, "editor":"person5", "name":"OPEN_ORDERS", "value":200 }, { "edit_tm":1457550081, "editor":"person5", "name":"RANDOM_STATUS", "value":2500 }, { "edit_tm":1457550, "editor":"person5", "name":"RANDOM_STATUS", "value":2500 } ], "rules":[] }, { "condition":{ "name":"RANDOM_STATUS", "pattern":"XDFS" }, "edit_tm":1457550081, "editor":"person4", "id":14, "limits":[ { "edit_tm":145755008, "editor":"person3", "name":"OPEN_ORDERS", "value":300 } ], "rules":[] } ] }
expected output:
[ { "hierarchyPath": ["0"], "condition":{ "name":"ROOT", "pattern":"" }, "id":0, }, { "hierarchyPath": ["0", "0_limits"], < "0" being the index of the element in this array and "limits" being the unique identifier "edit_tm": 324234, "editor": "person1", "name": "NAME", "value" :0 }, { "hierarchyPath": ["0", "0_rules"], < "0" being the index of the element in this array and "rules" being the unique identifier "condition":{ "name":"RANDOM_STATUS", "pattern":"*" }, "edit_tm":1457550081, "editor":"person2", "id":12 }, { "hierarchyPath": ["0", "12", "0_limits"], < "0" being the index of the element in this array and "limits" being the unique identifier "edit_tm":1457550081, "editor":"person3", "name":"RANDOM_STATUS", "value":50 }, { "hierarchyPath": ["0", "12", "1_limits"], < "0" being the index of the element in this array and "limits" being the unique identifier "edit_tm":1457550081, "editor":"person3", "name":"RANDOM_STATUS", "value":50 }, { "hierarchyPath": ["0", "12", "2_limits"], < "0" being the index of the element in this array and "limits" being the unique identifier "edit_tm":1457550081, "editor":"person4", "name":"RANDOM_STATUS", "value":50 }, { "hierarchyPath": ["0", "12", "3_limits"], < "0" being the index of the element in this array and "limits" being the unique identifier "edit_tm":145755008, "editor":"person5", "name":"OPEN_ORDERS", "value":200 }, { "hierarchyPath": ["0", "12", "4_limits"], < "0" being the index of the element in this array and "limits" being the unique identifier "edit_tm":1457550081, "editor":"person5", "name":"RANDOM_STATUS", "value":2500 }, { "hierarchyPath": ["0", "12", "5_limits"], < "0" being the index of the element in this array and "limits" being the unique identifier "edit_tm":1457550, "editor":"person5", "name":"RANDOM_STATUS", "value":2500 }, { "hierarchyPath": ["0", "14"] "condition":{ "name":"RANDOM_STATUS", "pattern":"XDFS" }, "edit_tm":1457550081, "editor":"person4", "id":14 }, { "hierarchyPath": ["0", "14", "0_limits"], < "0" being the index of the element in this array and "limits" being the unique identifier "edit_tm":145755008, "editor":"person3", "name":"OPEN_ORDERS", "value":300 } } ]

is this python code using BFS or any other searching algorithm?
hi I am working on this python code and wanted to know which searching algorithm its using to find goal state. I want to know if the following code is using BFS or any other searching algorithm this code is solving classic farmer, wolf, cabbage, goat problem
initial = ['L', 'L', 'L', 'L'] goal = ['R', 'R', 'R', 'R'] stack = [] stack.append(initial) def nextState(state): if state == goal: return False farmer = state[3] for i, s in enumerate(state): if s == farmer: tryState = makeState(state, i) if testState(tryState) and isUnique(tryState): stack.append(tryState) return True return False def makeState(s, i): t = [] for x in s: t.append(x) t[3] = 'R' if t[3] == 'L' else 'L' if t[3] == 'L': if not testState(t): t[i] = 'R' if t[i] == 'L' else 'L' else: t[i] = 'R' if t[i] == 'L' else 'L' return t def testState(s): if s[0] == s[1] and s[3] != s[0]: return False if s[1] == s[2] and s[3] != s[1]: return False return True def isUnique(s): if s in stack: return False return True while nextState(stack[1]): pass for i, x in enumerate(stack): print (i) print (x)

How to solve tuple object has not attribute solve?
I was given a task to solve a puzzle(in python) where i have an unlimited water resources and 3 bottles. Bottle A is 10ml, Bottle B is 6 ml and Bottle C is 5 ml.My start state would be 10 for bottle a and 0 for bottle b and c respectively. I have followed the guidelines provided by my tutor but i seem to get the following error
  AttributeError Traceback (most recent call last) <ipythoninput761c4e536d16e7> in <module>() 1 2 #run the program > 3 Bottle.main() <ipythoninput7563ac045619e7> in main() 160 def main(): 161 bot = Bottle(10,6,5), (10,0,0), (8,0,0) > 162 b = bot.solve(self) 163 for i in b: 164 print(i) AttributeError: 'tuple' object has no attribute 'solve'
Below are my codes:
#globals found = False states=[] class Bottle: def __init__(self, capacity, startState, goalState): self.capacity = capacity self.startState = startState self.goalState = goalState # ADD SOLVERS HERE self.Solver = Solver1() #self.Solver = Solver2() #self.Solver = Solver3(self, startState, goalState) def solve(self): global found self.visited = [] #visited node self.Solver.add(self.startState) #add the state to the solver state_eval = self.Solver.get() #visit/solve this state cost = 0 print("") print("\n Start State:", self.startState, "\n Goal State:", self.goalState) print("") while not (found): # we only continue if we're not at the goal if state_eval != self.goalState: temp = self.chooseAction(state_eval) print("\n Exploring State", state_eval) #add into self.visited if never visited if(state_eval not in self.visited): self.visited.append(state_eval) for i in temp: if not (i in self.visited): self.Solver.add(i) # add to visi hited self.visited.append(i) yield i if (i == self.goalState): print("\nReach Goal State:", i) found = True break state_eval = self.Solver.get() #get new state to visit else: print("Found goal state.") found = True yield "Task Completed" # Operators def chooseAction(self, state_eval): #fill up bottles if(b1 < 10 and found == False): #print("filled b1") state = (10, b2, b3) states.append(state) elif(b2 < 6 and found == False): #print("filled b2") state = (b1, 6, b3) states.append(state) elif(b3 < 5 and found == False): #print("filled b3") state = (b1, b2, 5) states.append(state) #empty the bottles if(b1 > 0 and found == False): #print("empty b1") state = (0, b2, b3) states.append(state) if(b2 > 0 and found == False): #print("empty b2") state = (b1, 0, b3) states.append(state) if(b3 > 0 and found == False): #print("empty b2") state = (b1, b2, 0) states.append(state) #transfer from one bottle to another if(0 < b2 + b3 >= 6 and b3 > 0 and found == False): #print("transfer from b3 to b2") state = (b1, 6, b3  (6  b3)) states.append(state) if(0 < b1 + b3 >= 10 and b3 > 0 and found == False): #print("transfer from b3 to b1") state = (10, b2, b3  (10  b3)) states.append(state) if(0 < b1 + b2 >= 10 and b2 > 0 and found == False): #print("transfer from b2 to b1") state = (10, b2  (10  b2), b3) states.append(state) if(0 < b1 + b2 >= 6 and b1 > 0 and found == False): #print("transfer from b1 to b2") state = (b1 (6  b1), 6, b3) states.append(state) if(0 < b1 + b3 >= 5 and b1 > 0 and found == False): #print("transfer from b1 to b3") state = (b1  (5  b1), b2, 5) states.append(state) if(0 < b2 + b3 >= 5 and b3 > 0 and found == False): #print("transfer from b2 to b3") state = (b1, b2  (5  b2),5) states.append(state) #Pour all the content of the bottles if(0 < b2 + b3 <= 6 and b3 >= 0 and found == False): #print("transfer all from b3 to b2") state = (b1, b2 + b3, 0) states.append(state) if(0 < b1 + b3 <= 10 and b3 >= 0 and found == False): #print("transfer all from b3 to b1") state = (b1 + b3, b2, 0) states.append(state) if(0 < b1 + b2 <= 10 and b2 >= 0 and found == False): #print("transfer from b2 to b1") state = (b1 + b2, 0, b3) states.append(state) if(0 < b1 + b2 <= 6 and b1 >= 0 and found == False): #print("transfer from b1 to b2") state = (0, b1 + b2, b3) states.append(state) if(0 < b1 + b3 <= 5 and b1 >= 0 and found == False): #print("transfer from b1 to b3") state = (0, b2, b1 + b3) states.append(state) if(0 < b2 + b3 <= 5 and b2 >= 0 and found == False): #print("transfer from b2 to b3") state = (b1, 0, b2 + b3) states.append(state) return state_eval def main(): bot = Bottle(10,6,5), (10,0,0), (8,0,0) b = bot.solve() for i in b: print(i) #run the program Bottle.main()

Coding exercise for practicing adjacency list and BFS
I have a coding exercise with a row of trampolines, each with a minimum and maximum "bounciness". I have the index of a starting trampoline and an end trampoline, and with this, I need to find the minimum amount of jumps required to reach the end trampoline from the start trampoline.
I have tried creating an adjacencylist, in which I list all possible jumps from a trampoline. This is fine until I reach a large number of trampolines. The Problem is it takes O(n^2) time. This is how I create the Adjacency List:
def createAL (a, b, l): al = [list() for _ in range(l)] for i in range(l): for j in range(a[i], b[i]+1): if (i+j) <= l1: al[i].append(i+j) if (ij) >= 0: al[i].append(ij) for i in range(len(al)): al[i] = list(set(al[i])) return al
"a" is the min. bounciness, "b" the max bounciness and "l" is the length of the two lists.
As you can see, the problem is I have 2 nested loops. Does anyone have an idea for a more efficient way of doing this? (preferably wo/ the loops)