Questions tagged [binary-tree]

A tree data structure in which each node has at most two child nodes.

binary-tree
Filter by
Sorted by
Tagged with
15 votes
2 answers
11k views

Binary Trees, arrays vs linked

In general, binary tree based abstractions can be implemented either using actual linked node objects, where each node has pointers to it's two children, or an array, where the children of node in ...
Taylor Huston's user avatar
15 votes
2 answers
2k views

Sort BST in O(n) using constant memory

This is not a homework. Just an interesting task :) Given a complete binary search three represensted by array. Sort the array in O(n) using constant memory. Example: Tree: 8 ...
gtikok's user avatar
  • 1,139
14 votes
3 answers
49k views

cannot cast to java.lang.Comparable

Although this question has already been asked but I have an implementation specific doubt. I am trying to print the top view of the binary tree and following is the complete code for it: import java....
pkenil96's user avatar
  • 183
14 votes
1 answer
3k views

Scala: Tree Insert Tail Recursion With Complex Structure

I'm creating a tree of custom objects in scala and my insert method throws a stack overflow because it's not tail recursive. However, I can't quite figure out how to make it tail recursive. Related ...
The.Anti.9's user avatar
14 votes
2 answers
10k views

Real world pre/post-order tree traversal examples

I understand pre-order, in-order, and post-order tree traversal algorithms just fine. (Reference). I understand a few uses: in-order for traversing binary search trees in order, pre-order for cloning ...
Plutor's user avatar
  • 2,887
14 votes
2 answers
8k views

Breadth First Search Traversal VS Pre-order Traversal VS Depth First Search Traversal

For a binary tree, is Breadth First Search traversal (BFS) the same as Pre-order traversal? I am a little bit confused by these two different types of traversals. Additionally, how does Pre-order ...
Liu's user avatar
  • 433
13 votes
6 answers
10k views

Lowest Common Ancestor of a Binary Tree

This is a popular interview question and the only article I can find on the topic is one from TopCoder. Unfortunately for me, it looks overly complicated from an interview answer's perspective. Isn't ...
user183037's user avatar
  • 2,559
13 votes
4 answers
16k views

Binary Tree in Objective-C

I am learning algorithms and data structures and to train I am trying to design and implement a binary tree using objective-c. So far I have the following Classes: main - for testing Node - node of ...
Janusz Chudzynski's user avatar
13 votes
20 answers
13k views

Trying to print top view of a tree using two if statements

Problem Statement You are given a pointer to the root of a binary tree. Print the top view of the binary tree. You only have to complete the function. My Code: void top_view(Node ...
Charan's user avatar
  • 1,061
13 votes
7 answers
5k views

For a given binary tree find maximum binary search sub-tree

For a given binary tree, find the largest subtree which is also binary search tree? Example: Input: 10 / \ 50 150 / \ ...
gtikok's user avatar
  • 1,139
13 votes
11 answers
18k views

How to convert a binary tree to binary search tree in-place, i.e., we cannot use any extra space

How to convert a binary tree to binary search tree in-place, i.e., we cannot use any extra space.
bit-question's user avatar
  • 3,803
12 votes
2 answers
54k views

Number of leaf nodes in full binary tree

Problem Find the number of leaf nodes in a full binary tree with n nodes. I wrote a recursive program for the above problem, traversing the tree and increasing the count of leaf nodes whenever I ...
user avatar
12 votes
5 answers
17k views

How to make binary tree from array in javascript?

I have an array var array = [8,10,12,5,3,6]; Logic First node would be root node. If new node value is less or equal =< than parent node, It would be left node of parent node If new node value is ...
Devendra Gokhe's user avatar
12 votes
3 answers
2k views

Do not understand the solution for the Binary Tree Maximum Path Sum problem

The website GeeksforGeeks has presented a solution for the problem of Maximum path sum for a binary tree. The question is as follows: Given a binary tree, find the maximum path sum. The path may ...
a_sid's user avatar
  • 587
11 votes
1 answer
9k views

Prove that binary trees with the same inorder and preorder traversals are identical?

Does anybody know how to prove that if two binary trees have the same inorder and preorder traversals, then they are identical? (perhaps by showing that you can't have two different binary trees with ...
erjiang's user avatar
  • 44.9k
11 votes
3 answers
2k views

Is a red-black tree my ideal data structure?

I have a collection of items (big rationals) that I'll be processing. In each case, processing will consist of removing the smallest item in the collection, doing some work, and then adding 0-2 new ...
Hugo van der Sanden's user avatar
11 votes
6 answers
36k views

how to find the height of a node in binary tree recursively

path = 0 # the lenght of the path while self.right != None or self.left != None: while self.right != None: self = self.right path = path +1 while self.left ...
Tural Gulmammadov's user avatar
11 votes
2 answers
13k views

Handling duplicates keys within an AVL tree

I want to make my avl-tree support duplicate keys but there is a problem with the default behavior of the binary search tree with duplicates that the rotation could make nodes with equal key be on the ...
Ahmed Kotb's user avatar
  • 6,287
11 votes
6 answers
89k views

What is the degree of a tree? (As in, a tree ADT) [closed]

I understand that the degree of a node is the number of children it has. However, how do we define the degree of a tree?
user avatar
10 votes
5 answers
36k views

Inserting an element in Binary Tree

Tried exploring a lot over the net, but could get any help, Everywhere its like adding a node to the Binary Search tree. Question: Requesting for algorithm and code snippet for adding a node to the ...
Raa's user avatar
  • 431
10 votes
5 answers
3k views

Binary Tree Transfer

How to transfer a binary tree (not a balanced tree) across two different systems efficiently, retaining its complete structure?
Avinash's user avatar
  • 119
9 votes
3 answers
1k views

Is there an existing solution for these particular multithreaded data structure requirements?

I've had the need for a multi-threaded data structure that supports these claims: Allows multiple concurrent readers and writers Is sorted Is easy to reason about Fulfilling multiple readers and one ...
thr's user avatar
  • 19.3k
9 votes
6 answers
3k views

Algorithm to Render a Horizontal Binary-ish Tree in Text/ASCII form

It's a pretty normal binary tree, except for the fact that one of the nodes may be empty. I'd like to find a way to output it in a horizontal way (that is, the root node is on the left and expands to ...
Justin L.'s user avatar
  • 13.6k
9 votes
4 answers
6k views

Randomly select a node from a Binary Tree

My tree class: public class BT<E>{ E value; BT<E> left, right; public BT(E value) { this.value=value; } public BT (E value, BT left, BT right) { ...
RK2015's user avatar
  • 397
9 votes
6 answers
11k views

How to build an incomplete binary tree from array representation

if the input is an array, where null means no node. input: [1, 2, 3, null, 5, null, 7] Please assume that I have already checked the input. For each array[i], its parents array[i / 2] will not be ...
Shihao Xu's user avatar
  • 1,190
9 votes
3 answers
887 views

Why is inorder and preorder traversal useful for creating an algorithm to decide if T2 is a subtree of T1

I'm looking at an interview book and the question is: You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a ...
But I'm Not A Wrapper Class's user avatar
9 votes
3 answers
5k views

Removing duplicate subtrees from binary tree

I have to design an algorithm under the additional homework. This algorithm have to compress binary tree by transforming it into DAG by removing repetitive subtrees and redirecting all these ...
xan's user avatar
  • 1,053
8 votes
3 answers
8k views

Confused - Height of Binary tree

I'm somewhat confused between the logic of calculating the height of binary tree. Code 1 public static int findHeight(Tree node) { if(node == null) return 0; else { return 1+...
tmgr's user avatar
  • 1,187
8 votes
2 answers
3k views

How to finding first common ancestor of a node in a binary tree?

Following is my algorithm to find first common ancestor. But I don’t know how to calculate it time complexity, can anyone help? public Tree commonAncestor(Tree root, Tree p, Tree q) { if (covers(...
dojoBeginner's user avatar
8 votes
1 answer
15k views

Saving a Binary tree to a file [closed]

I have a non-balanced (not binary-search) binary tree Need to incode (and later decode) it to txt file. How can I do it in efficient way? I found this link which talks about similar (same) problem,...
YAKOVM's user avatar
  • 10k
8 votes
1 answer
12k views

Binary Tree Using PHP + MySQL

I am implementing an MLM tree for a website using PHP (CodeIgniter) and MySQL. I need a binary tree implementation in the database. The followings things are to be considered: For each node , ...
Shahed Khan's user avatar
8 votes
1 answer
5k views

B Tree Index vs Inverted Index?

Here is mine understanding about both B Tree index :- It is generally used database column. It keeps the column content as key and row_id as value . It keeps the key in sorted fashion to quickly ...
emilly's user avatar
  • 10.3k
8 votes
10 answers
6k views

Finding the common ancestor in a binary tree

This question was asked to me in an interview: I have a binary tree and I have to find the common ancestor (parent) given two random nodes of that tree. I am also given a pointer to the root node. ...
Vijay's user avatar
  • 66.4k
7 votes
2 answers
22k views

Converting an infix expression (with parentheses) into a binary tree

As part of a Java assignment, I have to take an input arithmetic expression and store it in a binary tree. I have done everything necessary for the assignment except for the part where I read in the ...
HesNotTheStig's user avatar
7 votes
5 answers
6k views

Why use heap instead of binary tree when implementing priority queue?

It seems to me that the only advantage of heap over binary tree is to find the smallest item in the heap in complexity of O(1) instead of O(log(2)n) in binary tree. When implementing priority queue ...
Shelef's user avatar
  • 3,777
7 votes
2 answers
10k views

Is Red-Black tree balanced

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 ...
Ashot Khachatryan's user avatar
7 votes
2 answers
3k views

Binary tree that stores partial sums: Name and existing implementations

Consider a sequence of n positive real numbers, (ai), and its partial sum sequence, (si). Given a number x ∊ (0, sn], we have to find i such that si−1 < x ≤ si. Also we want to be able to change ...
Philipp's user avatar
  • 48.9k
7 votes
4 answers
9k views

Implementing Binary Tree in Ruby

I've been trying to implement BinaryTree class in Ruby, but I'm getting the stack level too deep error, although I don't seem to be using any recursion in that particular piece of code: 1. class ...
Maputo's user avatar
  • 983
7 votes
4 answers
39k views

Code with explanation for binary tree rotation (left OR right)

I have been trying to wrap my brain around how to write code for rotation of binary tree. I looked at http://en.wikipedia.org/wiki/Tree_rotation and enfuzzled.com I have been staring at this for 2 ...
user560871's user avatar
7 votes
5 answers
5k views

IntervalTree DeleteNode Java Implementation

I need an IntervalTree or RangeTree implementation in Java, and am having trouble finding one with working deletion support. There's a built-in one at sun.jvm.hotspot.utilities.IntervalTree, but the ...
Sam Barnum's user avatar
  • 10.6k
7 votes
3 answers
640 views

Rewrite a C code in Java to construct full binary tree

I want to write a function to construct a full binary tree from a given preorder and postorder array. I found that link http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-...
salamanka44's user avatar
7 votes
1 answer
13k views

Proof that a binary tree with n leaves has a height of at least log n

I've been able to create a proof that shows the maximum total nodes in a tree is equal to n = 2^(h+1) - 1 and logically I know that the height of a binary tree is log n (can draw it out to see) but I'...
MandyLB's user avatar
  • 317
7 votes
2 answers
16k views

Find a loop in a binary tree

How to find a loop in a binary tree? I am looking for a solution other than marking the visited nodes as visited or doing a address hashing. Any ideas?
novice's user avatar
  • 111
7 votes
2 answers
1k views

What python code generates all possible groupings (trees) for binary operators

As explained in several SO questions, and more abstractly at mathworld, the sequence of Catalan numbers happens to correspond to the number of parenthetical groupings that can be generated for any ...
Joe Golton's user avatar
7 votes
7 answers
21k views

How can I calculate the level of a node in a perfect binary tree from its depth-first order index?

I have a perfect binary tree, i.e. each node in the tree is either a leaf node, or has two children, and all leaf nodes are on the same level. Each node has an index in depth-first order. (E.g. in a ...
hrehfeld's user avatar
  • 480
6 votes
5 answers
6k views

What is the most efficient way to build an unsorted binary tree in java?

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; ...
Alex's user avatar
  • 2,179
6 votes
1 answer
2k views

Understanding the logic in iterative Postorder traversal implementation on a Binary tree

I was trying to understand how it is so intuitive to implement postorder traversal using 2 stacks. How did someone come up with it, is it just an observation or some particular way of thinking which ...
anjkhade's user avatar
6 votes
2 answers
2k views

Binary search tree traversal that compares two pointers for equality

I'm reading the Cormen algorithms book (binary search tree chapter) and it says that there are two ways to traverse the tree without recursion: using stack and a more complicated but elegant ...
Valentin V's user avatar
  • 25.4k
6 votes
6 answers
3k views

Detect cycles in a genealogy graph during a Depth-first search

I'm loading horse genealogical data recursively. For some wrong sets of data my recursion never stops... and that is because there are cycles in the data. How can I detect those cycles to stop ...
Romias's user avatar
  • 14k
6 votes
1 answer
2k views

represent binary search trees in python

how do i represent binary search trees in python?
Bunny Rabbit's user avatar
  • 8,323

1
3 4
5
6 7
11