What is the space complexity of storing a path ie. nodes of a binary tree from root to a particular leaf in an array? Basically, I am looking for space complexity of the following algorithm: public void printPath () { doPrint(root, new ArrayList<TreeNode>()); } private void doPrint(TreeNode node, List<TreeNode> path)...

Dealing with balanced and unbalanced binary trees. height = 0, possible trees = 1 (nothing) height = 1, possible trees = 1 (leaf) height = 2, possible trees = 3 I'm looking at the Catalan function but it has not lead me anywhere beneficial, mostly because I think it might...

I've seen approaches on how to iterate through binary trees and find the sum of all nodes, except I'm evaluating expression inputs for a calculator. The nodes are arranged in the proper order according to order of operations and the nodes are either operators or operands. I think recursion is...

So Basically I am trying to "populate" a file with 10^3 completely random numbers, so I could add them later to a Binary search tree. Here is the populate function I worked on so far: void populateFile(BinarySearchTree b) { int random_integer; srand( time( NULL ) ); std::ofstream myfile; string line;...

Ok, so the problem that I am trying to find is why when I call print_inOrder(), I don't get anything printed back. The assignment I am suppose to do is write a tree algorithm in descending order (meaning higher values on left and lower values on the right). I had...

I want to get the maximum width of a Binary tree. In this method using Pre-order traversal width can be calculated. But I can't understand it properly. Please explain how the function getMaxWidthRecur() works. // A utility function that returns maximum value in arr[] of size n int getMax(int arr[],...

Alright so I need to define a recursive function longest_length() that takes a binary string tree and returns the length of the longest string in the tree. I admittedly have no clue how to do this, but this is what I have set up: def add_leaves(bnt): """Takes a BNT and...

I have this challenging exercise I got from a book about c++, and i'm not sure how to tackle this problem. I must define a function called treeNodeCount() which returns the number of nodes in a binary tree (easy enough), and I also have to define an overloaded function that...

The table below represents a tree stored in a computer's memory. Each node of the tree contains three cells. The first cell contains the data to be stored; the second cell contains a pointer to the first cell's left child, and the third cell contains a pointer to the first...

This method suppose to add Node to a Binary Tree. I dont understand why it doesnt do it and where I have mistake. root is stay on null anytime. public void add(int num) { add(num, root); } private void add(int num, Node t) { if (t == null) t =...

My table structure is: id name parent lft rgt 1 abc 0 2 3 2 def 1 4 5 3 geh 1 6 7 4 ijk 2 8 9 5 lmn 2 10 11 What I am doing is fetching all records first and then searching tree for all possible...

I want to define an infinite tree in Haskell using infinitree :: Tree, but want to set a pattern up for each node, defining what each node should be. The pattern is 1 more then then its parent. I am struggling on how to set up a tree to begin...

This is the implementation of add in Binary Search Tree from BST Add private IntTreeNode add(IntTreeNode root, int value) { if (root == null) { root = new IntTreeNode(value); } else if (value <= root.data) { root.left = add(root.left, value); } else { root.right = add(root.right, value); } return root;...

I want to create an Arraylist of array which consist of treeNodes. My trial was ArrayList<Arrays<treeNode>> aList = new ArrayList<Arrays<treeNode>>(); Arrays<TreeNode> aNodes = new ArrayList<TreeNode>(); But it gives an error. (utils are included) What is the right way of writing this? My aim is to find the minimum depth of...

I was trying to learn about binary trees and NullPointerExceptionwere coming. So I decided to write a little program to try to understand it. Here is the code: public class Nulls { static Node node; private class Node { int val; Node right; Node left; } public void init(Node n)...

This is from Heap lecture slide 8. Add, peek, and remove make sense to me as to why those operations are O(log n)- traversing through BST cuts tree in half after each move. Can anyone explain the intuition behind the last sentence though, that "The tree tends to become unbalanced...

I am trying to make a very simple binary tree in Scala for data storage and traversal. Right now I have: trait Tree case class Node(left: Tree, value: String, right: Tree) extends Tree My questions: How can I also include a pointer to a parent? Can I have left and...

I'm working on a a function that check whether an element is part of a binary tree. I've defined a type for my tree called Tree, functions to get the root element and the left and right subtrees, and a function called isElement for checking whether a value is into...

I was reading about the rope data structure on wikipedia and I was a little confused about the description. Wiki link: http://en.wikipedia.org/wiki/Rope_(data_structure) Description A rope is a binary tree having leaf nodes that contain a short string. Each node has a weight value equal to the length of its string...

How is it possible to write generic c? I started writing a collection of balanced trees (scapegoat, splay, aa and so on) and find many things in common. Example is destroy function found below. Can such function and those similar be defined with void pointers without causing "dereferencing void* pointer...

I understand AVL and Red Black are implementations of self balancing trees. But I'm curious how difficult it would be actually create a near as possible self balancing tree. To the point where the height could only be off my one node in no more than 1 branch. This would...

I have the following Binary tree 3 / \ 5 2 / \ / 1 4 6 My weekness is recursion, so please bear with me, and I need your help to trace through it to get it right. I have the following code, and what it does is print...

I need to create an unsorted binary tree (one requirement is that it is unsorted) that holds a String as its value. My class outline looks like this: public class Node { private String desc; private Node leftNode = null; private Node rightNode = null; public Node(String desc) { this.desc...

Given a binary tree, whose root is located a treasure, and whose internal nodes can contain a dragon or does not contain anything, you are asked to design an algorithm that tells us the leaf of the tree whose path to the root has the lowest number of dragons. In...

The method I have written below is supposed to act on a BinaryTreeNode to flatten the tree 'beneath' that node. My if-else if-else together with a recursive (?) structure, to my understanding, will always return a value, but I am getting an error in Eclipse saying "This method must return...

Setup: I have a list of numbers that represent a Binary tree. The first number is treated differently than some of the rest, it is the root. Out of "the rest" of the numbers, some will be higher than the root, some will be lower. Higher numbers are ordered to...

I came across this problem that has Ternary expression (a?b:c) and needs the ternary expression to be converted into a Binary tree structure. a?b:c a / \ b c a?b?c:d:e a / \ b e / \ c d My approach using a Binary tree implemented using a array :-...

I have a binary tree like - 1 / \ 3 5 / \ 7 9 Now I'm trying to represent the tree using HashTable. So I have created a HashTable binaryTree - HashTable binaryTree = new HashTable<Integer, Intgeger>(); Then I am trying to add item to the binaryTree. I...

Here is a simple binary tree in c, but it seems not balance, how to make it balance? Code: /** * binary_tree impl */ #include <stdio.h> #include <stdlib.h> typedef struct _tnode _tnode; typedef struct _bin_tree _bin_tree; struct _tnode { int data; _tnode *parent; _tnode *left; _tnode *right; }; _tnode *new_node(int...

I'm intentionally creating a wrong and unbalanced binary tree in this code: void createlist (tree*& node) { node = new tree; node->num = 1; node->left = new tree; node->left ->num = 2; node->right = new tree; node->right->num = 3; node->left->left = new tree; node->left->left->num = 4; node->left->right = new tree;...

I'm struggling with following problem: Write function which for given binary tree returns a root of minimal height which is not BST or NIL when tree is BST. I know how to check if tree is BST but don't know how to rewrite it. I would be grateful for an...

Consider this example of binary search tree. n =10 ;and if base = 2 then log n = log2(10) = 3.321928. I am assuming it means 3.321 steps(accesses) will be required at max to search for an element. Also I assume that BST is balanced binary tree. Now to access...

I have a report which shows 2-4 million records. I get the records from oracle to java and push it to an excel report. All this is already done! Now, I also need to add a new tab with top 10 and last 10 records. What would be the best...

I have this tree structure sealed trait Tree case class Node(var left: Tree, var right: Tree, var value: String) extends Tree case object EmptyNode extends Tree and a Tree object called myTree. I want to make another tree with the exact same structure and values called otherTree, but myTree.clone() does...

I'm trying to write an implementation of a BinaryTree whose object can be of any type that implements Comparable. However, I realize that won't completely work. For example, A String and a Double wouldn't be able to be inserted into the same tree, even though they both implement Comparable. So,...

I've made an implementation of binary tree in python and wanted to see if it works with isEmpty function. When I tested the code and inserted some values I've notised, that python is somehow deleting values from the tree, because if I check if the root equals None I get...

I have written a couple of functions to calculate size of binary tree. The first one (Function 1) works perfectly fine and is declared outside the class, it is not a member function of the class. However the second one which is the member function of the class is giving...

i have this code: #include <stdio.h> #include <stdlib.h> typedef struct node{ struct node* next; int data; }NODE; NODE* makeNode (int x){ NODE* new; new = (NODE*)malloc(sizeof(NODE)); new -> data = x; new -> next= NULL; return new; } typedef NODE* linkedlist; void insertnode (NODE** node, int x){ if(!(*node)) *node=makeNode(x); else...

I'm a little confused why my code doesn't insert nodes past the first one. say I wanted to insert (5,4) after (7,2) using the code below; in this case the very first condition is triggered, isVertical and p.x() < node.point.x(). The way I see it since node.left is null, I...

Node is a very simple class with a just a constructor and a few variables: a "name" (actually just a char) and two child Node pointers called "left" and "right". I was just starting to write some code that needs to drop to the left-most node, and I was quite...

Is it possible to create a function that takes a list of elements of any imaginable type and returns an operator that can act as a comparator for ordering the elements? In other words, template typename<T> ??? getComparator ( T a ) { // ... } where I put ???...

I have tried implementing same in c++. I think I almost got it.However I am getting an error while accessing node from a linked list. list<list<Node*> > Binary_Tree::level(Node* node) { list<Node*> current,parent; list<list<Node*> > result; list<Node*>::iterator itr; if (node != NULL) current.push_back(node); while(current.size() > 0) { result.push_back(current); parent = current;...

Recently, my questions were marked duplicate, like this , even if they weren't. So, let me start with following and then I'll explain my question. Why this question is not a duplicate? I'm not asking how to create a binary tree when inorder & preorder traversal are given. I'm asking...

I tried this, but I am getting compile time error. What I am missing ? I also have to return false if the element not found public boolean search(Node root, Node node){ if(root==node){ return true; } if(root.getLeft()!=null){ search(root.getLeft(), node); } if(root.getRight()!=null){ search(root.getRight(), node); } } ...

I am trying to insert node in a binary tree using recursive method. But once its out of the method the root becomes the new node and left child and right child are null. With this I'm trying to learn how recursion works. Also, does recursive method always has to...

I want to find a saddle point of T, binary tree, if there is one. saddle point has minimum value among all its ancestors, but it has maximum value among all its descendants. A leaf can be such a saddle point, if it has a lower value than all of...

I am making a binary tree from given inorder and preorder traversal array and I don't know why it is giving me the wrong output although it works perfectly for some points in the given array #include<iostream> using namespace std; class Node { public: int i; Node* left; Node* right;...

I have been working on creating a Binary Tree from scratch, not using built-in libraries. I am working on a function called "pruneLeaves". The job is to remove all leaves of the tree; nodes with no children. When I step through the function with breakpoints, it appears to be removing...

So my coding exercise is given the reference to the node count its children. I've decided to use recursion and I was wondering is this a elegant way to do this: Let's assume there is class Node which represent every node in the tree: public Node { int data: Node...

I am trying to use the Haskell Diagrams library for drawing binary trees. This is my tree type: data Tree a = Empty | Node { label :: a, left,right :: Tree a } leaf :: a -> Tree a leaf a = Node a Empty Empty This is a...

I have these instance methods in my Java implementation of Binary Tree and Search Binary Tree: getSize(), getHeight(), getDepth(), getPreOrder(), getInOrder(), getPostOrder() and getLevelOrder(). These methods use the root of the tree in others recursive methods that have a parameter Node. Which is more appropiate to use from the point...

I am trying to find the largest value in a binary search tree. The sample solution is given below, but I'm trying to understand if there's anything wrong with my solution? My problem with the sample solution is that it seems to check whether each node is not None twice:...

I'm trying to make a BST tree structure in C but I'm having some difficulty getting my insert function working. After reading some examples, I've discovered that the best way to go about it is by passing in a pointer to the root of the tree and then recursively inserting...

I have a tree setup. I am trying to save it into a txt file using a BufferedWriter. It creates the file, then it runs into a null pointer exception when my program first calls the write method of the BufferedReader(line 102), so I guess its not getting initialized properly?...

Okay so i am trying to pass an array of chars through a function, then assign that string of chars to the member of a structure for a binary search tree. my files are to be split up and i cant seem to figure out what i am doing wrong....

How to write a correct inorder-method for my binary-tree implementation? This is my test-try: class Main { public static void main(String[] args) { BinaryTree myTree = new BinaryTree(); myTree.inorder(0); } } public class BinaryTree { char[] tree = {'k', 'q', 'r', 'g', 'e', 'i', 'y', 'p', 'l', 'b', 'x', 'm',...

REFERENCE I am copy pasting the problem and the solution that works in C, I am not able to get this working in Java. I understand primarily it is because in Java parameters are passed by value and that is causing problem to maintain state of "old_value". But I even...

Giving you a binary tree which defined as follows: public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = this.right = null; } } print the total sum of all the path, a path is defined as the line from...

This falls under "a software algorithm" from http://stackoverflow.com/help/on-topic This is from an interview question http://www.glassdoor.com/Interview/Yelp-Software-Engineering-Intern-Interview-Questions-EI_IE43314.0,4_KO5,32_IP2.htm, particularly "performance of binary tree if implemented thru array or linkedlist" How would you go about implementing a binary tree via an array or a linked list? The way I was taught to do it...

What manipulations are we doing in insert/delete that we aren't in mirror? By mirror I'm referring to switching the left and right child of every single node in the tree. The reason I'm asking is that when it comes to an insert, if you don't save the root returned by...

I am trying to compare two strings to see where it should go as a leaf node from the root and so fourth. I keep trying to use string compare and I get an error. I am very unfamiliar with binary trees in c and need help inserting nodes. Here...

I have been asked in an interviews to print the boundary of the Binary Tree. For example. 1 / \ 2 3 / \ / \ 4 5 6 7 / \ \ 8 9 10 Answer will be : 1, 2, 4, 8, 9, 10, 7, 3 I have...

I am trying to convert an integer array into a binary tree using C. For example for an array a[10]={5,2,1,6,7,3,4} , the Binary tree should look like 5 / \ 2 1 /\ /\ 6 7 3 4 I tried to convert using the following code typedef struct btree {...

I am studying red-black trees and I am reading the Cormen's "Introduction to Algorithms" book. Now I am trying to create red-black tree with numbers 1-10 by using the pseudo-code described in the book - RB-INSERT-FIXUP(T, z). Here is the screenshot Everything was fine until I inserted number "6" into...

I am working on a practice data structures problem from Heap Practice The objective is to make a constructor for a min heap with a given array. The author already gives us the high level algorithm to do so, "If you just "bubble down" all of the non-leaf nodes of...

I am writing a Binary Tree. On trying to delete a node that has two children, I have written a method which searches for the most left node of the right child's branch. I am getting a strange error - before returning the value, I seem to go into the...

I have the following binary tree structure, and I'd like to write a function that calculates and return the average depth of objects in a tree. Here is what I'm trying to do: calculate the total height of the tree divide total height/total nodes However, I'm getting nowhere, and would...

Suppose we have a binary tree and a linked list that holds the data that appears in all of the leafs. For example, the following tree's list would be: 9,2,3 (order matter, left to right) Now we add a new node somewhere, thus creating a new branch, like so: Is...

I want to create a math expression parse tree from an array that is sorted in prefix notation. (BTW, will it be easier with postfix?) For example: Infix: ((((3+4)*5)/2)+8) Prefix: + 8 / 2 * 5 + 4 3 (the function will be given this) Below is my code, in...

The program creates a binary search tree from a sorted array of numbers and adds elements to it. struct Tree { Tree *left_son, *right_son; int head, key; }; Tree *tree(int *a, int left, int right) { Tree *tree1 = new Tree; int mid = middle(left,right); tree1->head = a[mid]; if (left...

I know how to insert integers into binary search tree Smaller to the left Larger to the right But that formula would be applicable only if Data/Key is integer. So i want to know how do i insert strings into BST I have searched the google but couldn't find any...

But I ran into a challenge when I took an exam some days ago. If we have balanced binary tree with n vertices and store the number of children in the sub-tree for each node (i.e number of children that this node as a root has). How we can do...

I am trying to tokenize a textfile and then put the tokens in a binary tree where the token that has a lower value goes on the left branch of the tree and the token that has a higher value goes to the right and repeated values have an updated...

I need some help in C Help me to extend the binary tree sort on C. I need to return a sorted array in sort function. here it is: #include <stdio.h> #include <stdlib.h> struct btreenode { struct btreenode *leftchild ; int data ; struct btreenode *rightchild ; } ; void...

can you please explain to me what is a balanced binary tree i read many explanations and still didn't get. and can we say that a complete binary tree is a balanced binary tree? according to Wikipedia : A balanced binary tree has the minimum possible maximum height (a.k.a. depth)...

In the following code I have written a insertion function for a binary tree. But after each call it doesn't inserting any node to the tree. I have checked the algorithm for insertion in a binary tree. I think there is some pointer issue but can't figure it out why...

How to remove the root of a binary tree? private static NodeClass remove(int deleteThisItem, NodeClass item) { deleted=false; if(item==null) return item; /////////////////////////////////////////// if(deleteThisItem<item.value) item.left=remove(deleteThisItem,item.left); else if(deleteThisItem>item.value) item.right=remove(deleteThisItem,item.right); /////////////////////////////////////////////// deleted=false; if(item==null) return item; /////////////////////////////////////////// if(deleteThisItem<item.value)...

How do we determine if a given tree T contains subtree that is isomorphic to another tree S? Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any...

I have been trying to convert a list of lists format to a binary tree object which consists of nodes and references. So far, I have a 3 cases where the left and right node is empty, left is empty and right is empty. The problem is that whenever I...

I have this algorithm, A and B are the addresses of of two different binary trees' roots. Each node has a value, pointer to left sub-tree and pointer to right sub-tree. Here is the algorithm: foo(A,B){ if (A == NULL){ return B; } if (B != NULL){ if(A->value > B->value){...

I saw anwser here but i dont have Object Empty and i have leaf not just everthing in Node like this : case class Node ( val e : Int ,left : BinaryTree, right : BinaryTree). I have problem with adding Leaf as param in this def sums. import scala.annotation.tailrec...

HERE is the c++ implementation for right view of binary tree without using queue. When I try to convert it to Java, it is not working. Here is my Java code: (I think most likely it is because I have not understood the algorithm properly and handling of maxLevel pointers/reference)...

I am having trouble with a function in my C program. The purpose of the program is to: Read integers from a binary file into an array Sort these numbers using a binary tree Do some other stuff Free all memory that you allocated using malloc(); I've got everything working...

I have faced this question in an interview. Given a binary tree, find the longest path length with at most one turn. one end of the path has to be a leaf. Other end can be a leaf or any node. Turn is defined as: In tree1-> start from 1...

I know what Binary search tree is and I know how they work. But what does it take for it to become a skewed tree? What I mean is, do all nodes have to go on one side? or is there any other combination? Having a tree in this shape...

I'm learning Scala by working the exercises from the book "Scala for the Impatient". Given the following way to model binary trees with case classes, one question asks to compute the sum of all elements in the leaves. sealed abstract class BinaryTree case class Leaf(value: Int) extends BinaryTree case class...

For class, I have to create a binary tree of state objects, each of which includes a binary tree of resident objects organizing the people who live in each state. I'm trying to search a given state for its oldest resident; however, the residents are organized in the tree by...